零知识证明大整理

  学的内容多了，就可以搞个总结整理了。
  慢慢填坑。

  推荐一个 2019 年的 camp 可以学到多数 ZKP 经典内容。
  其他参考资料：Sanjeev Arora 的经典教材《Computational Complexity: A Modern Approach》，以及各类密码学教材。

初始 Fundamental

  Princeton 的这个 lec15 和 lec16 是非常好入门教程。

  怎么说明一个输入 $x$ 属于一个语言 $L$ 呢？通常来说，就是写出来一个数学证明（通常就是给出 $x$ 的 witness），谁想知道谁就来看。但缺点就是把 witness 公开出来了，有没有不公开的方法呢？比如有一个门禁，门禁里有一个大整数 $n$，我的“钥匙”就是 $n$ 的质因数分解。如果我直接显式地输入 $n$ 的质因数分解，那就会被人偷看偷听了，有没有方法使得我既能让门禁相信我知道 $n$ 的质因数分解，又能不说出任何关于 $n$ 质因数分解的信息呢？

  零知识证明(Zero-Knowledge Proof, ZKP)是一个交互协议，交互双方为 Prover、Verifier，其中 Verifier 计算能力有限（通常假设它只有多项式时间）。它们会得到一个输入 $x$，Prover 想让 Verifier 相信 $x$ 属于某个语言 $L$。这个交互协议满足如下条件：

• Completeness：如果 $x \in L$，那么 Verifier 以高概率接受；
• Soundness：如果 $x \not \in L$，那么 Verifier 以高概率拒绝；
• Zero-Knowledge：Verifier 经过交互以后没有得到额外的信息，即，整个交互过程可以被 Verifier 自己模拟出来。更确切地说，存在一个算法 Simulator，它可以模拟出一个 Verifier 的 view，该 view 与真实交互中 Verifier 的 view 是不可区分的。（不可区分可以是完美/统计/计算不可区分）

  给非 CS 背景的人科普时可以举的通俗易懂的例子：如下图，Alice 想要给 Bob 证明她拥有这个门的钥匙，但不能直接把钥匙给她看。方法是，Bob 站在顶上通道处，每次随机喊“左”或“右”，Alice 就必须从下方走到对应位置。过程重复若干次，如果 Alice 总是能成功，Bob 就能确信 Alice 拥有钥匙了。但 Bob 没有亲自看到这把钥匙或是开门过程。

  给非 CS 背景的人科普时可以让他看的视频。（油管链接，需科学上网）

  给 CS 背景的人科普时可以举的例子：图同构。有两幅图 $A$ 和 $B$，Prover 希望 Verifier 相信 $A$ 和 $B$ 同构。每次操作 Prover 给 Verifier 发送一个新图 $C$（由 $A$ 点标号随机打乱而来），声称 $A,B,C$ 同构，Verifier 要么询问 $A$ 和 $C$ 之间的点标号映射，要么询问 $B$ 和 $C$ 的点标号映射。操作重复若干次，Verifier 接受当且仅当每次 Prover 都能正确回答问题。
  如果 $A,B$ 真的同构，那么 Prover 总是能正确回答。如果 $A$ 和 $B$ 不同构，那么 Prover 每次最多只有 $\frac 12$ 的概率回答正确，重复若干次以后概率无限小。直观理解，Verifier 每次只是知道了 $A$ 或 $B$ 其中一幅图的点标号重排结果，从中并不能推断出更有用的信息。

  想要细学的话需要了解的例子：二次剩余、3-Coloring、哈密顿回路。

更多框架

随机自归约(Random Self-Reducible)问题的ZKP

  如果你发现二次剩余、离散对数、图同构的 ZKP 都长得很像，那么 [TW87] 这篇文章就可以告诉你，这不是巧合。它们都是 random self-reducible 的，于是可以设计出统一的 ZKP 框架，并且是 perfect ZKP 的：

• 输入：$x$，诚实的 Prover 拥有其 witness $y$。
• Prover 随机生成一个 $r \in \{0,1\}^*$，将 $(x,y)$ 用 $r$ 随机归约成 $(x',y')$，发送 $x'$。
• Verifier 发送一个随机提问 $b \gets_R \{0,1\}$。
• 若 $b=0$，Prover 发送 $r$，Verifier 检验“$x$ 用 $r$ 归约成 $x'$”；若 $b=1$，Prover 发送 $y'$，Verifier 检验“$y'$ 是 $x'$ 的 witness”。

  例如，在二次剩余中，$x \equiv y^2 \pmod n, x' \equiv x \cdot r^2 \pmod n, y' \equiv yr \pmod n$；在离散对数中，$x \equiv g^y, x' \equiv g^{y+r}, y' \equiv y+r$。

  其实不仅是 random self-reducible，只要能把 $A$ 问题随机归约到 $B$ 问题，就能对 $A$ 问题采用这个框架。

  这个东西的一个很重要的意义在于，结合后续一系列推导（包括 $\mathsf{SZK \subseteq coAM}$、$\mathsf{NP\subseteq coAM} \Rightarrow \text{polynomial hierarchy collapses}$），可以得到 $\mathsf{NPC}$ 问题不能拥有 SZK，又或者拥有 SZK 的问题（比如 random self-reducible 的问题）不能是 $\mathsf{NPC}$。

$\sum$-Protocol

带各种特性的零知识证明

常数轮零知识证明 Constant-Round Zero-Knowledge Proof

  传统的 ZKP 是把一个协议串行执行很多次来降低 soundness，因此自然会想如果把它改成并行，就变成常数轮了。但简单的并行会使得 simulator 的时间复杂度爆炸。（例如很多 ZKP 是让 verifier 发送两种询问中的一种，simulator 原本只需要期望 $2$ 步猜对询问然后往下走，现在 $n$ 个询问并行，那么就变成期望 $2^n$ 步才能同时猜对然后往下走。）
  [GK96] 的 idea 是：还是并行，但让 verifier 先把询问加密发送给 prover，再执行原协议，到该询问的时候让 verifier 解密。这样 simulator 就不用猜询问了，一直发垃圾等 verifier 自己解密了询问再时间倒流即可。具体来说（以哈密顿回路的 3 轮协议为例）：

• Verifier 将询问串用 computationally binding, perfectly hiding 的 commitment scheme 加密发送给 Prover。
• Prover 发送原协议第一步的消息。
• Verifier 解密询问串。
• Prover 回答。

细节分析很复杂，因为要考虑各种不遵守协议 halt 的情况，如果不明白某些步骤的意义，可以参考 《Tutorials on the Foundations of Cryptography》6.5.4 节的讲解。

  [GK96] 的缺点就是不遵守协议 halt 的情况太复杂，其中有一个分析就是由于 simulator 会倒车，导致 verifier 有至少两次解密询问，如果每次成功解密的概率不一样，就会使得 simulator 期望倒车次数爆炸。
  [Ros04] 这篇仍然是让 verifier 先发送询问（假设叫 $\sigma$），但是额外生成了 $\sigma_i^0,\sigma_i^1$ 使得 $\sigma_i^0 \oplus \sigma_i^1=\sigma$。它让 prover 解密 $\sigma_i^0,\sigma_i^1$ 中的其中一个，这对 prover 来说是没有用的，但是 simulator 可以在这里倒车获得询问，这样就没有“每次成功解密的概率不一样”的问题，因而期望倒车次数是常数。
  由于发送询问的方式更复杂了，所以轮数变成了 7 轮，没有达到最优，但是分析简单了很多。

非交互零知识证明 Non-Interactive Zero-Knowledge Proof

  把 ZKP 做成非交互的当然是一个美好的愿景了，这样可以大大提升 ZKP 的效率，从而提高实用性。

  但如果就简单地只是让 Prover 发条消息给 Verifier，这是不可能的。

Lemma: 如果问题 $L$ 存在一个 ZKP 只是让 Prover 发一条消息给 Verifier，那么 $L \in \mathsf{BPP}$。

  证明：对于输入 $x$，直接让 simulator 模拟一个 Prover 消息，用 Verifier 验证，这就得到了 $L$ 的概率多项式算法。

  事实上，不只是一轮不行，参考 Lower Bound of ZKP，黑盒 simulator 的情况下三轮都不行。

  因此要实现非交互，必须借助一些外部工具。一个可行的方法就是 Common Reference String (CRS)，从天上来了一个可信第三方，给出了一个符合特定分布的字符串，Prover 和 Verifier 都无条件相信这个字符串是符合特定分布的。这个信任，就可以用来实现非交互。
  下表是使用 CRS 的一些经典方法的总结。

Paper	Problem	Extra Property	CRS represents	Assumption	Completeness	Soundness	ZK	len of CRS
[KT92]	3-Coloring		2 numbers for each edge	hardness of Quadratic Residuosity	$1$	$0$	computational	$16k$
[FLS99]	Hamiltonian	-	a cycle	One-Way Permutation with hard-core predicate	$1$	$neg$	computational	$n^7k^2m$
[FLS99]	Hamiltonian	argument		One-Way Trapdoor Permutation
[FLS99]	$\mathsf{NPC}$	multiple provers	random $y$ and original CRS	Psseudorandom Generator (from $n$-bit to $2n$-bit)				$2n + \vert CRS \vert$
[KP98]	3-SAT-5		wild strings and random strings	Hidden Bit Model	$1-neg$	$neg$	computational	$O(kn \log (n/\epsilon))$
[GOS12]	circuit SAT		commitment scheme	Homomorphic Commitment Scheme	$1$	$0$	computational	$O(1)$
[WP22]	Linear Problems, circuit SAT		commitment scheme in matrix	$\mathsf{NC^1 \subsetneq \oplus L/poly}$	$1$	$0$	$\mathsf{NC^1}$ computational	$\lambda^2$

  另一种方法是 Fiat-Shamir Transform，即如果 verifier 发的消息全都是随机字符串，那么就用一个伪随机函数来代替掉它，伪随机函数的输入就是之前的所有消息。

非黑盒零知识证明 Non-Black-Box Zero-Knowledge Proof

理论相关

Lower Bound of ZKP

ZKP and One-Way Function

  [Ost91] 及后续工作 [Ost93] 提出的思路，我猜是在考虑怎么用 simulator 产生的 view 来设计判定 $x \in L$ 的算法的时候，捣鼓出了这个玩意。
  如果一个问题 $L$ 是属于 $\mathsf{SZK}$ 的，并且是 hard on average 的，那么就可以通过这个 SZK 构造出 one-way function。这个 one-way function 的输入是 SZK 里的 simulator 所需的 random tape，输出是 simulator 产生的 view of verifier。
  证明大致是，假设这个函数不是 one-way 的，即输入 view 可以快速求出 random tape。那么用 simulator 充当 prover，与 verifier 交互（每得到一条 verifier 的消息就重新算 random tape，再用 simulator 计算出 prover 要发的消息），这样就得到了 $L$ 的快速判定算法，从而 $L$ 不是 hard on average。
  为什么限定是 SZK 呢？因为 SZK 证明 correctness 的时候会方便很多。后续论文 [Ost93] 把这个思想拓展到一般 ZKP 上了。
  为什么是 hard on average 呢？我认为这个条件是不准确的，它用反证法推翻的结论是“$L$ 没有高效的概率算法”，所以应该跟 [ZKP-OWF] 一样，是“不属于 $\mathsf{BPP}$”。

$\mathsf{SZK}$ and $\mathsf{coAM}$

Reference

• [FLS99] Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple noninteractive zero knowledge proofs under general assumptions. In SIAM Journal on computing 1999.
• [GK96] Oded Goldreich, and Ariel Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. In Journal of Cryptography 1996.
• [GOS12] Jens Groth, Rafail Ostrovsky, and Amit Sahai. New techniques for noninteractive zero-knowledge. In Journal of the ACM 2012.
• [KP98] Joe Kilian, and Erez Petrank. An efficient noninteractive zero-knowledge proof system for NP with general assumptions. In Journal of Cryptology 1998.
• [KT92] Kaoru Kurosawa, and Kenichi Takai. A comment on NIZK for 3 colorability. In ICCS/ISITA `92.
• [Ost91] Rafail Ostrovsky. One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. In CCC 1991.
• [Ost93] Rafail Ostrovsky, and Avi Wigderson. One-Way Functions are Essential for Non-Trivial Zero-Knowledge. In Israel Symposium on Theory and Computing Systems 1993.
• [Ros04] Alon Rosen. A Note on Constant-Round Zero-Knowledge Proofs for NP. In Theory of Cryptography 2004.
• [TW87] Martin Tompa, and Heather Woll. Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information. In STOC 1987.
• [WP22] Yuyu Wang, and Jiaxin Pan. Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security. In EUROCRYPT 2022.