💻 computer science

Weak Zero-Knowledge and One-Way Functions

该论文证明了若 NP 中所有语言均存在具有非可忽略误差的弱零知识证明（满足特定误差和小于 1 的条件），则单向函数必然存在，从而将此前关于弱零知识协议与单向函数存在性之间关系的研究结论推广到了更广泛的误差参数范围。

原作者： Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

发布于 2026-02-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文探讨了一个非常深奥的密码学问题：如果我们能证明某些极其困难的问题（比如破解密码或解决复杂的数学难题）是“几乎”无法被破解的，那么这是否意味着我们一定能构建出安全的加密系统？

为了让你轻松理解，我们可以把这篇论文的核心思想想象成一场**“魔术表演”与“侦探破案”**的游戏。

1. 核心角色：魔术、侦探与“弱”规则

零知识证明 (Zero-Knowledge, ZK)：想象一个魔术师。他向观众（验证者）证明他手里有一把钥匙能打开一个宝箱，但他绝不展示钥匙，也不透露宝箱里有什么。观众看完表演后，确信魔术师有钥匙，但除了“他有钥匙”这个事实外，一无所知。
困难语言 (Hard Languages)：这是那些极其难解的谜题。比如，给出一幅画，问“这幅画里有多少种颜色？”如果画是随机生成的，数清楚可能很难；但如果画是精心设计的，可能很容易。密码学希望找到那些“对普通人来说很难，但对有钥匙的人很容易”的谜题。
单向函数 (One-Way Functions, OWF)：这是密码学的基石。想象一个单向的碎纸机。你把文件放进去，很容易变成碎片（正向计算）；但如果你想把碎片拼回原文件（逆向计算），几乎是不可能的。如果这种“碎纸机”存在，我们就能构建安全的密码系统。

2. 以前的困境：完美的“弱”魔术

以前的研究认为，只有当魔术师的表演完美无缺时（即：观众几乎不可能被骗，观众也几乎不可能猜出秘密），我们才能推导出“碎纸机”的存在。

但在现实生活中，很多魔术表演是**“弱”的**：

失误率 ( $\epsilon_c$ )：魔术师偶尔会手滑，证明失败。
欺骗率 ( $\epsilon_s$ )：偶尔有骗子能蒙混过关。
泄密率 ( $\epsilon_z$ )：偶尔观众能猜出一点点秘密。

以前的研究（如 2025 年的 Chakraborty 等人）发现，如果这些错误加起来稍微小一点（比如 $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ ），就能推导出“碎纸机”。但这就像说：“只有当魔术师的失误率小于 10% 且欺骗率小于 1% 时，我们才相信有碎纸机。”这限制太死了，很多有用的魔术都被排除在外。

3. 这篇论文的突破：更宽松的“弱”规则

这篇论文的作者（Rohit, Yunqi, Prashant）做了一件很酷的事情：他们把门槛降到了最低。

他们证明了：只要这些错误加起来小于 1（即 $\epsilon_c + \epsilon_s + \epsilon_z < 1$ ），哪怕错误率高达 49%、49% 和 1%，只要总和没超过 100%，我们就依然能推导出“碎纸机”（单向函数）的存在！

通俗比喻：
想象你在玩一个“找茬”游戏。

旧规则：只有当魔术师犯错、骗子成功、观众猜对秘密的总概率非常非常低时，我们才相信世界是安全的。
新规则：作者说，只要这三件事发生的总概率不到 100%（也就是说，总有一点点机会是魔术师赢了，或者骗子输了，或者观众没猜对），这就足够证明世界上存在“碎纸机”了。

这意味着，即使是非常“笨拙”或“不完美”的零知识证明协议，只要它不是完全没用的（总和小于 1），它背后就隐藏着强大的密码学力量。

4. 他们是怎么做到的？（技术魔法的简化版）

作者使用了一种**“递归侦探”**的策略：

构建陷阱：他们设计了一个特殊的函数（就像设计了一个特殊的碎纸机），这个函数的输出包含了魔术表演的记录。
利用倒推：假设有人能轻易破解这个函数（即能轻易从碎片还原文件），那么这个人就能利用这个能力，去模拟那个魔术表演。
发现矛盾：
- 如果这个谜题（语言）是真的很难的（没人能解），那么这个模拟者应该无法成功骗过验证者。
- 但是，如果破解者存在，模拟者就能骗过验证者。
- 这就产生了矛盾！
结论：既然矛盾了，说明“破解者”不存在。因此，那个函数就是单向函数（碎纸机）。

关键创新点：
以前的方法在模拟时，需要检查两次“是否成功”，这会导致错误率加倍（就像你检查两次，每次都有 10% 的误差，总误差就变大了）。
作者的新方法非常巧妙，他们把“验证”这一步直接嵌入到了函数内部。就像侦探在破案时，不再需要事后去核对证据，而是直接在寻找线索的过程中就确认了线索的有效性。这样，他们省掉了一次错误率的惩罚，从而把条件从 $\sqrt{\epsilon_s}$ 放宽到了 $\epsilon_s$ ，甚至对于多轮互动，也找到了更优的公式。

5. 不同的场景，不同的结果

论文还讨论了两种不同的互动模式：

非交互式 (NIZK)：魔术师发一张纸条，观众看一眼就信。
- 结果：只要错误总和小于 1，就能得到标准的“碎纸机”（非常安全）。
多轮互动 (Public-Coin ZK)：魔术师和观众来回对话好几轮（比如 3 轮、5 轮）。
- 结果：如果轮数是固定的（常数轮），且错误总和小于 1，我们能得到**“无限次”**的“碎纸机”。
- 注：“无限次”的意思是，虽然不能保证对所有长度的输入都安全，但对无限多的长度是安全的。这虽然比“标准”弱一点，但在密码学里已经是非常强的保证了。

6. 总结与意义

一句话总结：
这篇论文告诉我们，零知识证明不需要完美无缺。只要它不是“完全没用”的（即错误率总和小于 100%），它就足以作为构建现代密码学大厦（单向函数）的基石。

这对我们意味着什么？

更广泛的适用性：以前很多因为“不够完美”而被认为没有密码学价值的协议，现在被证明是有用的。
理论更坚固：它填补了理论上的空白，让我们对“困难问题”和“加密安全”之间的关系有了更清晰、更完整的认识。
未来的方向：虽然已经很强了，但作者也留下了开放问题，比如能否把“无限次安全”变成“完全安全”，或者如何处理更复杂的互动模式。

这就好比以前我们认为只有“纯金”才能做成硬币，现在发现，只要合金里含金量超过一定比例（哪怕不是纯金），它依然可以流通，依然有价值。这篇论文就是那个重新定义“含金量”标准的发现。

这篇论文《弱零知识性与单向函数》（Weak Zero-Knowledge and One-Way Functions）由 Rohit Chatterjee、Yunqi Li 和 Prashant Nalini Vasudevan 撰写，主要研究了弱零知识（Weak Zero-Knowledge, ZK）协议对**最坏情况困难语言（Worst-case hard languages）的蕴含关系，特别是这些协议如何推导出单向函数（One-Way Functions, OWFs）**的存在性。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

零知识协议与密码学基础：零知识协议是现代密码学的核心。传统的零知识协议通常要求完备性（Completeness）、可靠性（Soundness）和零知识性（Zero-Knowledge）的错误率都是可忽略的（negligible）。
弱零知识协议：许多自然且实用的协议（如 3-着色、图非同构）原生具有非可忽略的错误率（即 $\epsilon_c, \epsilon_s, \epsilon_z$ 可能是常数）。这些被称为“弱”零知识协议。
核心问题：
1. 如果 NP 中的所有语言都存在满足特定非可忽略错误参数的弱零知识协议，是否足以推导出单向函数（OWF）的存在？
2. 现有的结果（如 Chakraborty et al., CRYPTO 2025）对错误参数有较严格的限制（例如 $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ ）。能否将这些条件放宽到最一般的非平凡情况（即 $\epsilon_c + \epsilon_s + \epsilon_z < 1$ ）？
3. 对于多轮公共硬币（Public-coin）协议，其错误参数的界限如何？

2. 主要贡献与结果 (Key Contributions & Results)

论文在假设 NP 中存在最坏情况困难语言（即 $NP \not\subseteq ioP/poly$ ）的前提下，得出了以下三个主要定理：

定理 1：非交互式零知识（NIZK）

条件：如果 NP 中所有语言都存在 $(\epsilon_c, \epsilon_s, \epsilon_z)$ -NIZK 证明或论证，且满足 $\epsilon_c + \epsilon_s + \epsilon_z < 1$ 。
结论：单向函数（OWFs）存在。
意义：这是最一般的情况，覆盖了所有非平凡的错误率组合。此前已知结果需要 $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ 。此外，如果 $\epsilon_c$ 是可忽略的，该结果还意味着所有错误均可被放大为可忽略错误。

定理 2：多轮公共硬币零知识（一般轮数）

条件：如果 NP 中所有语言都存在 $t$ -消息的 $(\epsilon_c, \epsilon_s, \epsilon_z)$ -公共硬币 ZK 协议，且满足 $\epsilon_c + \epsilon_s + (t-1) \cdot \epsilon_z < 1$ 。
结论：单向函数（OWFs）存在。
对比：传统的 Ostrovsky-Wigderson 方法会给出 $\epsilon_c + \epsilon_s + t \cdot \epsilon_z < 1$ 的条件，本文通过改进技术将零知识误差的系数从 $t$ 降低到了 $t-1$ 。

定理 3：常数轮公共硬币零知识

条件：如果 NP 中所有语言都存在 $k$ -轮（ $k$ 为常数）的 $(\epsilon_c, \epsilon_s, \epsilon_z)$ -公共硬币 ZK 协议，且满足 $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ 。
结论：无限次单向函数（Infinitely-often OWFs）存在。
注意：虽然参数条件比定理 2 更优（系数为 $k$ 而非 $2k-1$ ），但结论仅保证“无限次”成立的 OWF，而非标准 OWF。这是因为证明过程中需要多个逆算子同时成功，导致输入长度的重叠性限制。

3. 方法论与技术路线 (Methodology)

论文的核心思想是将“弱零知识协议”转化为“辅助输入单向函数（ai-OWF）”，进而推导出标准 OWF。

A. 从弱 ZK 到辅助输入单向函数 (Reductions to ai-OWF)

这是论文最核心的技术突破，主要改进了 Ostrovsky-Wigderson (OW93) 的构造。

OW93 方法的局限性：
- 传统构造定义函数 $f_x(\rho) = \text{Sim}(x; \rho)$ 的输出（即模拟的公共参考串 $r$ 和证明 $\pi$ ）。
- 为了区分语言，构造器需要运行验证器 $V$ 。如果 $x \in L$ ，模拟生成的 $(r, \pi)$ 被 $V$ 接受的概率至少是 $1-\epsilon_z$ 。
- 如果 $x \notin L$ ，任何高效算法生成被接受的 $\pi$ 的概率至多是 $\epsilon_s$ 。
- 问题：在分析中，为了利用零知识性质，通常需要两次涉及 $\epsilon_z$ 的界限（一次用于模拟分布与真实分布的不可区分性，一次用于验证步骤），导致条件变为 $\epsilon_s + 2\epsilon_z < 1$ （或更差）。
本文的改进构造：
- 关键洞察：将验证器 $V$ 的输出直接嵌入到候选单向函数的输出中，从而避免在区分器中显式地再次运行 $V$ 带来的额外零知识误差惩罚。
- 新函数定义：
  $f_x(\rho) : (r, \pi) \leftarrow \text{Sim}(x; \rho); \quad a \leftarrow V(x; r, \pi); \quad \text{output } (r, a)$
- 分析逻辑：
  - 如果存在一个高效的逆算子 $A$ 能完美逆 $f_x$ ，则给定 $(r, 1)$ ， $A$ 能找到对应的 $\rho$ ，使得 $\text{Sim}(x; \rho)$ 生成的证明被 $V$ 接受。
  - 当 $x \in L$ ：由于零知识性，真实协议生成的 $(r, 1)$ 与模拟生成的 $(r, a)$ 分布不可区分（误差 $\epsilon_z$ ）。逆算子在模拟分布上成功，意味着在真实分布上也以高概率成功。接受概率 $\ge 1 - \epsilon_z$ 。
  - 当 $x \notin L$ ：根据可靠性（Soundness），任何算法生成被接受证明的概率 $\le \epsilon_s$ 。
  - 结论：只要 $\epsilon_s + \epsilon_z < 1$ ，就能构造出区分器。这消除了之前方法中额外的 $\epsilon_z$ 项。
多轮协议的递归构造：
- 对于多轮公共硬币协议，作者采用递归方法。
- 定义一系列函数 $f_{k,x}, f_{k-1,x}, \dots$ ，其中 $f_{i,x}$ 的输出包含前 $i$ 轮的消息以及一个估计值（Estimate），该估计值代表后续轮次能成功完成协议的概率。
- 通过逆算子 $A_i$ 来寻找能最大化后续成功概率的当前轮次消息。
- 这种递归结构允许在常数轮情况下将零知识误差的系数优化为 $k$ （而非 $2k-1$ ），但代价是证明是非黑盒的，且仅能推导出无限次 OWF。

B. 从 ai-OWF 到标准 OWF

利用 Hirahara-Nanashima [HN24] 和 Chakraborty et al. [CHK25] 的框架：
1. 证明 ai-OWF 的存在蕴含了“单边平均情况困难语言”（One-sided Average-Case Hard Languages）的存在。
2. 证明针对这类困难语言的弱 ZK 协议（满足上述误差条件）可以进一步推导出标准 OWF。
对于常数轮情况，由于递归构造的特性，最终得到的是无限次 OWF。

4. 技术细节与证明亮点

处理随机化验证：论文还讨论了当验证器 $V$ 是随机化的情况。通过计算期望值 $E[V(\cdot)]$ 并将其作为函数输出的一部分，同样可以推导出 $\epsilon_s + \epsilon_z < 1$ 的界限。
分布性逆算子（Distributional Inverter）：在证明中，作者使用了分布性逆算子的概念，即逆算子不仅要在统计上接近均匀分布，还要能正确恢复原像。这通过 Yao 和 Impagliazzo-Levin 的引理转化为标准 OWF。
三角不等式与数据处理不等式：在分析模拟分布、真实协议分布和逆算子输出分布之间的距离时，严格运用了统计距离和计算不可区分性的三角不等式及数据处理不等式，精确地追踪了误差项的累积。

5. 意义与影响 (Significance)

理论边界的完善：该论文将弱零知识协议蕴含单向函数的条件推到了理论极限（ $\epsilon_c + \epsilon_s + \epsilon_z < 1$ ）。这表明，只要零知识协议不是完全无意义的（即错误率之和小于 1），且 NP 是困难的，那么单向函数就必然存在。
参数优化：显著改进了之前工作的参数界限（去掉了 $\sqrt{\epsilon_s}$ 项，优化了多轮协议中的系数），使得更多自然存在的弱协议（如某些常数轮协议）被纳入 OWF 存在的推导范畴。
对密码学基础的启示：进一步巩固了“零知识性”与“单向函数”之间的深层联系。它表明，即使是非常“弱”的零知识性质，只要结合最坏情况的困难性假设，也足以构建现代密码学的基石（OWF）。
开放问题：
- 能否将常数轮协议的结果从“无限次 OWF"提升到“标准 OWF"？
- 私有硬币（Private-coin）弱 ZK 协议是否也能达到同样的界限？
- 超常数轮协议的误差界限能否进一步优化？

总结

这篇论文通过巧妙的函数构造和递归分析，解决了弱零知识协议参数界限的长期开放问题，证明了在极其宽松的错误率条件下，只要 NP 是困难的，单向函数就必然存在。这不仅完善了零知识理论，也为从弱假设构建强密码原语提供了更坚实的理论基础。