之前在本科的课程仅仅略微介绍了下零知识证明，之后自学了一些相关内容，但不成体系。本学期跟着邓老师较为系统地学习了 ZKP，发现自己之前有很多的误解，临近期末整理下重要内容。

参考文献：

1. Goldreich O. Foundations of cryptography: volume 2, basic applications[M]. Cambridge university press, 2009.
2. Arora S, Barak B. Computational complexity: a modern approach[M]. Cambridge University Press, 2009.
3. Feige U, Shamir A. Witness indistinguishable and witness hiding protocols[C]//Proceedings of the twenty-second annual ACM symposium on Theory of computing. 1990: 416-426.
4. Barak B. How to go beyond the black-box simulation barrier[C]//Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 2001: 106-115.
5. 国科大 《密码协议》课程 PPT

Traditional Proof System

传统的数学证明（traditional math proof system）：关于声明（Statement）$T$ 的一个证明（Proof）$w$（实际上是一个证据 witness），可以被一个 PPT 的图灵机 $M$ 判定：
$$M(T,w)=1⟺T\text{ is true}$$

其中 $|w|$ 的长度是多项式的。

由于 $L\subseteq NP$，那么存在 PPT 的关系 $R_L$，使得
$$\forall x,\exists y,|y|\le poly(|x|),R_L(x,y)=1$$

因此语言 $L$ 存在证明系统 $⟨P,V⟩$，无界的 $P$ 找出证据 $w$，PPT 的 $V$ 执行 $R_L$ 进行判断。即 $L\subseteq NP$ 当仅当 $L$ 有一个证明系统。

然而，传统的数学证明系统有些限制：proof 必须是短的，且 $V$ 可以学习到 witness 的知识。

Interactive Proofs

IP system

[Goldwasser, Micali, Rackoff, 85] 给出了交互式证明系统（Interactive proof system，IP），它包含 interaction 以及 randomness，可以达成以下性质：

1. Completeness（almost）
2. Soundness（almost）：随机性的引入，“almost” 是不可避免的
3. Enable us to prove much harder theorems to an efficient verifier
4. Zero knowledge：所谓 “知识” 就是 $V$ 没能力计算的，如果 $V$ 本身就有能力给出 witness，那么这种交互证明是没有任何意义的。

一个关于 $L$ 的 IP 系统是一对图灵机 $(P,V)$，满足以下性质

• $V$ 是 PPT 能力的

• 完备性：对于任意的 $x\in L$，都有
  $$Pr[(P,V)(x)=1]\ge c(n)$$

• 可靠性：对于任意的 $x\notin L$，任意的（无界）敌手 $P^{\ast }$，都有
  $$Pr[(P^{\ast },V)(x)=1]\le s(n)$$

  这里的 $s(n)$ 叫做 Soundness Error，我们要求 $c(n)-s(n)>\frac{1}{poly(n)}$，类似于 BPP 的概率放大，这等价于 $c(n)=1-negl(n)$，$s(n)=negl(n)$

• 当 $P^{\ast }$ 是 PPT 能力的非一致（non-uniform）敌手，如果对于充分长的 $x\notin L$ 此协议满足 soundness，我们称这个系统是 Interactive Argument（交互式论证）

Power of IP

我们定义语言类：
I P = { L : L  has an IP system } IP = \{L: L \text{ has an IP system}\} IP={L:L has an IP system}

由于传统数学证明系统属于 $IP$ 类，因此它包含 $NP$。事实上，$PSPACE=IP$（$NP,co\text{-}NP\subseteq PSPACE$），它的能力比传统数学证明系统强的多（大多数人都认为 $P\ne NP\ne PSPACE\ne EXPSPACE$）。

例如，传统数学证明系统没办法有效的证明 “定理 A 没有短证明”，因为这需要穷举所有的短字符串，并依次验证它们都不是定理 A 的正确证明。一个 statement 的 witness 可能会很长（在 $NP$ 之外），但是 IP 系统中的无界证明者 $P$，依然可以为 PPT 的验证者，提供一个短的 proof 使之相信它。例如下面的两个 $co\text{-}NP$ 类中的语言，
$$\begin{gathered} GNI:=\{(G_0,G_1):\forall \varphi ,\varphi (G_0)\ne G_1\} \\ QNR:=\{(x,n):\forall w,x\ne w^2(\mathrm{mod}n)\} \end{gathered}$$

可以给出 IP 系统 [Goldreich, Micali, Wigderson, 86]，

但是，实际上 $QNR\subseteq NP\cap co\text{-}NP$，因此它本身就存在短证明（找出 $n$ 的所有素因子，验证 $x(\mathrm{mod}{p}_i)\in QNR,\forall p_i$）。另外，虽然没有人能证明 $GNI\subseteq NP$，但是由于 $GI$ 存在亚指数的算法 [Babai17]，因此人们更愿意相信 $GI$ 属于 $P$ 类，此时 $GNI$ 也自然会属于 $P\subseteq NP$。所以，上述的两个例子似乎并没有那么令人吃惊。

[Fortnow, Sipser, 88] 证明了，对于 $co\text{-}NPC$ 语言
c o - S A T : = { CNF  ϕ : ∀ x i ∈ { 0 , 1 } , ϕ ( x 1 , ⋯   , x n ) = 0 } co\text{-}SAT := \{\text{CNF } \phi: \forall x_i \in \{0,1\},\phi(x_1,\cdots,x_n)=0\} co-SAT:={CNF ϕ:∀xi​∈{0,1},ϕ(x1​,⋯,xn​)=0}

仅使用相对化技术（relativization technique，内嵌的黑盒对 Oracle 的请求可以被 “bubble” 到任意的外层），IP 系统无法证明它。

但是不久之后，[Nisan90] 利用 Schwartz-Zippel Lemma 给出了算术化技术（Arithmetization），紧接着 [Shamir89] 就考虑 $PSPACE\text{-}complete$ 语言
{ CNF  ϕ : ∃ x 1 , ∀ x 2 , ⋯   , Q n x n ∈ { 0 , 1 } , ϕ ( x 1 , ⋯   , x n ) = 1 } \{\text{CNF } \phi: \exists x_1, \forall x_2, \cdots, Q_n x_n \in \{0,1\},\phi(x_1,\cdots,x_n)=1\} {CNF ϕ:∃x1​,∀x2​,⋯,Qn​xn​∈{0,1},ϕ(x1​,⋯,xn​)=1}

证明了 $PSPACE=IP$。后续，[Babai, Fortnow, 90] 给出了 $MIP=NEXP$ 的证明（proof 的伸缩），这就导出了 zkSNARK 中关键的 PCP theorem，我们可以类似 ECC 原理，将一个传统证明 $w$ “拉长抹匀” 成另一个证明 $\pi$，只需检查其中的少量比特就能以极高的置信度相信 proof 是正确的。

Zero Knowledge

一般而言，人们更关注对于 $NP$ 语言类的证明（仅仅 PPT 能力的 $V$ 没法读取指数长的证据）。我们现在考虑带有证据输入的证明者 $P(w)$，它的计算能力可以是无界的（proof system），也可以是 PPT 的（argument system）。

我们将 $⟨P(w),V⟩(x)$ 交互中传递的消息叫做 “副本”（Transcript） { x , m 1 , ⋯   , m k } \{x,m_1,\cdots,m_k\} {x,m1​,⋯,mk​}，我们将 $V$ 所看到的内容（包括它的 random tape）叫做 “视图”（View） { r V , t a n s c r i p t } \{r_V,tanscript\} {rV​,tanscript}

由于 ZKIP 系统可以视为特殊的 2PC 系统（$P$ 输入 $w$ 输出 $\perp$，$V$ 输入 $\perp$ 输出 $R_L(x,w)$），因此可以使用 2PC 的安全性定义给出 ZK 的安全性定义。注意到计算的 $R_L(x,w)$ 是确定性函数，并且 $P$ 的输出是 $\perp$，因此可以忽略联合分布中一部分。

我们说一个关于语言 $L$ 的 IP 系统 $(P,V)$ 有零知识性，对于任意的 non-uniform PPT 敌手 $V^{\ast }$，都存在一个 non-uniform PPT 模拟器（simulator）$Sim$，使得
{ S i m V ∗ ( x , z ) } x ∈ L , z ∈ { 0 , 1 } ∗ ≡ c { V i e w V ∗ ( z ) P ( w ) ( x ) } x ∈ L , z ∈ { 0 , 1 } ∗ \{Sim_{V^*}(x,z)\}_{x \in L,z \in \{0,1\}^*} \overset{c}{\equiv} \{View_{V^*(z)}^{P(w)}(x)\}_{x \in L,z \in \{0,1\}^*} {SimV∗​(x,z)}x∈L,z∈{0,1}∗​≡c{ViewV∗(z)P(w)​(x)}x∈L,z∈{0,1}∗​

其中 $z$ 是 auxiliary input（甚至可以是 witness），用于 ZKP 作为子协议嵌入到其他协议中时的归约使用（从协议执行中已经获得了一部分信息，这些信息不再被保护）。对于充分长的 $x\in L$，任意的 non-uniform PPT 区分器 $D$，都有
$$Pr[D(Si{m}_{V^{\ast }(z)}(x))=1]-Pr[D(Vie{w}_{V^{\ast }(z)}^{P(w)}(x))=1]\le negl(n)$$

如果上述两个分布簇是 perfect / statistical / computational indistinguishable，那么称这是 perfect / statistical / computational zero knowledge。

我们定义语言类
P Z K : = { L : L  has a perfect ZK proof system } PZK := \{L: L\text{ has a perfect ZK proof system}\} PZK:={L:L has a perfect ZK proof system}

由于 ZKP 中要用到承诺协议，soundness 对应于的 binding 性质，zero knowledge 对应于承诺协议的 hiding 性质，如果同时达成 proof 以及 perfect ZK，就需要

• 对于 false 实例 $x\notin L$，（类）承诺协议有 perfect binding
• 对于 ture 实例 $x\in L$，（类）承诺协议有 perfect hiding

这是一种实例依赖的（Instance-Dependent）承诺协议（perfect binding 和 perfect hiding 无法同时达到，无界敌手总可以打破其中之一）。

可以证明 $P\subseteq PZK$（不必交互，自然完美）以及 $GI,QR\subseteq PZK$（可以构造出它们的 PZK IP 协议），但是 [Fornow88] 证明 $NPC$ 极不可能属于 $PZK$，因此 $PZK$ 语言类很小。

不过，在标准假设（基于 DL 假设的拥有 perfect hiding 性质的 Pedersen Commitment Scheme）下所有的 $NP$ 语言都有 PZK arguments（汉密尔顿图 $HC\subseteq NPC$ 的 Blum 协议，以及 Karp-Levin Reduction $(f,g)$）。

Randomness

IP 系统的强大能力来源于随机性和交互能力 [Goldreich, Oren, 94]。

随机性：

• 如果语言 $L$ 拥有 computational ZK proof，其中的验证者 $V$ 是确定性的，那么 $L\subseteq RP$ 是 trivial 的。
• 如果语言 $L$ 拥有 computational ZK proof，其中的证明者 $P$ 是确定性的，那么 $L\subseteq BPP$ 是 trivial 的。

交互能力：

• 如果语言 $L$ 拥有 one-step ZK proof（也就是 NIZK，这儿的 ZK 是不含 auxiliary input 的较弱定义），那么 $L\subseteq BPP$ 是 trivial 的。
• 如果语言 $L$ 拥有 two-step perfect auxiliary input ZK proof 或者 two-step non-uniformly computational auxiliary input ZK proof，那么 $L\subseteq BPP$ 是 trivial 的。

因此 $V$ 的对于 $R_L(x,w)=1$ 的信心，关键在于它参与的随机化交互过程，而交互过程中 $P$ 给出的 proof 消息并没有包含这种信心（可以被 $Sim$ 有效模拟）！这也是为什么 Fiat-Shamir Transform 中必须引入 Random Oracle 来代替 $V$ 去投掷 public-coin 的原因（我们相信 RO 会给出 “随机的” 挑战）。

在 standard model 中 NIZK 不存在：我们必须引入 CRS model 或者 ROM model 来避免上述的不可能性。

Expected Poly-time

在证明 ZK 性质时，持有 $V^{\ast }$ 描述的模拟器 $Sim$ 为 $V^{\ast }$ 提供随机带 $r_V$ 使之运行（以 Black-box 方式），并为它模拟与 $P$ 的交互过程（不持有 $w$ 的 $Sim$ 如同 $P$ 一样工作），从而构造出与 $Vie{w}_{V^{\ast }(z)}^{P(x)}$ 不可区分的模拟视图。

由于 $Sim$ 并不知道 $V^{\ast }$ 的策略，因此 $V^{\ast }$ 发出的消息是不可预测的（虽然 $Sim$ 控制了 $V^{\ast }$ 的随机带）。$Sim$ 通过猜测 $V^{\ast }$ 发出的随机挑战，在承诺中放入可以使得 $V^{\ast }$ accept 的对应内容。如果猜错了，那么 $Sim$ 可以 rewind（回绕）抹除 $V^{\ast }$ 的记忆，重新为 $V^{\ast }$ 挑选新的随机带并继续猜测它的随机挑战（因为承诺中的内容改变了，固定 $V^{\ast }$ 的随机带没有意义）。

在这种 black-box 以及 using only rewinding 的策略下，模拟器的运行时间必然是 “期望” 多项式时间的（Expected Poly-time），无法做到 strict poly-time。但是 [Barak, Lindell, 02] 给出了 Barak’s Non-Black-Box Zero-Knowledge Protocol，它可以被一个严格多项式时间的 simulator 模拟。不幸的是，之后这些年来再没有更多有意思的 non-black-box 的进展。

在课程学习中遇到的所有 ZKP 构造，都是 black-box + rewind 的模拟器，归约过程中的重中之重，就是证明 $Sim$ 的期望运行时间是多项式（或者说，证明 $Sim$ 猜对的概率 $p$ 是显著的，从而根据帕斯卡分布的期望，$\mathbb{E}(time)=\frac{r=1}{p}$ 是个多项式）。

Composition

对于承诺协议的存在性，有如下结论：

1. 如果 DL 假设成立，则存在 2-round 的 perfect-hiding 以及 computational-binding 的承诺协议（二次剩余群上的 Pedersen Scheme）
2. 如果 OWF 存在，则存在 2-round 的 computational-hiding 以及 statistical-binding 的承诺协议（基于 PRG 的 Naor’s Scheme）
3. 如果 OWP 存在，则存在 1-round 的 computational-hiding 以及 perfect-binding 的承诺协议（基于 hardcore 的比特加密）

使用这些承诺协议来搭建 Blum’s ZK Protocol for HC，那么就有：

1. 如果 DL 假设成立，则任意的 $NP$ 语言都存在 4-round 的 perfect ZK argument，其 soundness error 为 $s.e.\le \frac{1}{2}+negl(n)$
2. 如果 OWF 存在，则任意的 $NP$ 语言都存在 4-round 的 computational ZK proof，其 soundness error 为 $s.e.\le \frac{1}{2}+negl(n)$
3. 如果 OWP 存在，则任意的 $NP$ 语言都存在 3-round 的 computational ZK proof，其 soundness error 为 $s.e.\le \frac{1}{2}+negl(n)$

WI

为了把 soundness error 降低到 $negl(n)$，需要多次独立执行（使用独立的随机带）IP 协议：重复 $n$ 次可以降低到 $1/2^n$，重复 ${\log }^{2}n$ 可以降低到 $1/n^{\log n}$。在协议的 general composition 中，多个并发（concurrent）协议的步骤可能出现交错（interleaving），这将带来一系列的问题，

• Sequential composition：保持 ZK 性质（模拟器可以在开始 next repetition 之前模拟每个 repetition），但是 round complexity 大幅上升。
• Parallel composition：情况较为复杂
  1. 在 proof system 下，并行 ZKP 可以降低 s.e 的同时依然保持 ZK，这是 works in general
  2. 在 argument system 下，[Chung, Pass, 10] 证明了对于 constant-round public-coin 的论证系统在降低 s.e 的同时保持 ZK，但是 not in general（例如 GMW for G-3C 的并行就不保持 ZK），这是个 Open Problem

[Feige, Shamir, 90] 介绍了新的安全性：证据不可区分（Witness Indistinguishable）、证据隐藏（Witness Hiding），并证明了 WI 在 general composition 下依然保持，同时对于 “或” 语言 $L^2:=L\vee L$ 的 WI Proof 也是 WH 的。

我们说一个语言 $L$ 的交互式 proof / argument 系统 $(P,V)$ 是证据不可区分的（WI），如果对于任意的 non-uniform PPT 敌手 $V^{\ast }$，任意的序列 $\{(x,w_0,w_1):(x,w_0),(x,w_1)\in R_L{\}}_{x\in L}$，都有
{ V i e w V ∗ ( z ) P ( w 0 ) ( x ) } x ∈ L ≡ c { V i e w V ∗ ( z ) P ( w 1 ) ( x ) } x ∈ L \{View_{V^*(z)}^{P(w_0)}(x)\}_{x \in L} \overset{c}{\equiv} \{View_{V^*(z)}^{P(w_1)}(x)\}_{x \in L} {ViewV∗(z)P(w0​)​(x)}x∈L​≡c{ViewV∗(z)P(w1​)​(x)}x∈L​
对于只有一个 witness 的声明 $x\in L$，上述定义是 trivial 的。WI 对于 composition 有着良好的兼容性：

1. 易知，ZK 立即导致 WI（分布簇不可区分性的传递）
2. 协议的并行执行保持 WI 性质（使用 Hybrid 技术，依次替换相邻的 repetition 所使用的 witness），论文中证明了 general composition 是保持 WI 的。
3. 于是任意 ZK IP（例如 Blum’s ZKP）的 $n$-parallelized 版本，都是 $s.e.=negl(n)$ 的 WI IP 系统。

WH

对于语言 $L\subseteq NP$，我们说分布簇 { X n  over  { x ∈ L : ∣ x ∣ = n } } n ∈ N \{X_n\text{ over }\{x \in L:|x|=n\}\}_{n \in \mathbb N} {Xn​ over {x∈L:∣x∣=n}}n∈N​ 是关于 $R_L$ 困难的（distribution of hard instances，原始论文中称之为 invulnerable generator），如果任意的 non-uniform PPT 敌手 $M$，都有
$$Pr[x\leftarrow X_n:M(x)\in R_L(x)]\le negl(n)$$

我们说一个语言 $L$ 的交互式 proof / argument 系统 $(P,V)$ 是关于分布簇 $\{(X_n,W_n)\text{ over }{R}_L{\}}_{n\in \mathbb{N}}$ 证据隐藏的（WH），如果对于任意的 non-uniform PPT 敌手 $V^{\ast }$，都有
$$Pr[⟨P(W_n),V^{\ast }(z)⟩(X_n)\in R_L(X_n)]\le negl(n)$$

现在，我们辨析下 WH 与 ZK，它们有两个明显的不同：

1. WH 的定义是依赖于分布簇 $X_n$ 的，对于同一个 $n$ 敌手的 auxiliary input 是相同的（而在 ZK 定义中 $z$ 可以依赖于 $x$）。即使 $P$ 公开了无限多的 $x^{\ast }\in L$ 对应的 witness，只要这些 $x^{\ast }\leftarrow X_n$ 被采样的概率可忽略，那么 IP 系统依然是 WH 的。
2. WH 仅仅确保 “whole” witness 不被泄露（类似于 OWF 和 hardcore 的关系），它允许泄露证据的部分信息（而 ZK 保证不泄露 witness 的任何信息）。这对于数字签名来说是个优势，因为严格来说数字签名不可以是 ZK 的（标准模型下的 NIZK 使得 $Sim$ 伪造出签名。而在 FS 转换中，模拟器可以 “编程” RO，而真实敌手没这个能力），但是数字签名可以是 WH 的（只隐藏那些允许真实签名者可以正确签名的信息）（这一段博主还是不太理解 ╥﹏╥，求大佬指教）

令 $L\subseteq NP$，对应的关系为 $R_L$，定义
L 2 = L ∨ L : = { ( x 0 , x 1 ) : ∃ i ∈ { 0 , 1 } , x i ∈ L } R L 2 : = { ( ( x 0 , x 1 ) , w ) : ∃ i ∈ { 0 , 1 } , ( x i , w ) ∈ R L } L^2 = L \vee L := \{(x_0,x_1): \exists i \in \{0,1\}, x_i \in L\}\\ R_{L^2} := \{((x_0,x_1),w): \exists i \in \{0,1\}, (x_i,w) \in R_L\} L2=L∨L:={(x0​,x1​):∃i∈{0,1},xi​∈L}RL2​:={((x0​,x1​),w):∃i∈{0,1},(xi​,w)∈RL​}

我们用语言 $L$ 上的 invulnerable generator 独立地采样两个困难实例 $(x_0,w_0),(x_1,w_1)\in R_L$，然后随机丢弃一个证据，就构造出了语言 $L^2$ 的一个困难实例 $((x_0,x_1),w_b)$

那么假如 $(P,V)$ 是关于 $L^2$ 语言的 WI 系统，那么 $(P,V)$ 也是关于 $R_{L^2}$ 上 hard distribution（其中的 $x_0,x_1$ 独立随机）的 WH 系统。归约过程中，假设与 $P(w_b)$ 交互后 $V^{\ast }$ 成功时总是输出 $w_b$，那么这就打破了 WI；假设与 $P(w_b)$ 交互后 $V^{\ast }$ 成功的条件下以显著占比输出 $w_{1-b}$，那么这就打破了 hard distribution（交互过程中根本就没有 $w_{1-b}$ 的信息）。

Proof of Knowledge

知识的证明（PoK）是 soundness 的强化，

1. [GMR85] 所谓 “知识”（Knowledge），就是 the output of an unfeasible computation for a specific machine（PPT 图灵机没能力处理的）
2. [Goldreich04] 所谓 “知道”（know），就是 it can be modified to a new machine that can outputs this secret（可以实际地输出）

我们说一个语言 $L$ 的 IP 系统 $(P,V)$ 是 proof（argument） of knowledge with knowledge error $ϵ(\cdot )$，如果对于任意（充分长）的 $x\in L$，任意的无界（PPT）敌手 $P^{\ast }$，假如
$$Pr[⟨P^{\ast },V⟩(x)=1]\ge p(|x|)>ϵ(|x|)$$

那么就存在一个 non-uniform PPT 提取器（Extractor）$Ext$，使得
$$Pr[Ex{t}^{P^{\ast }}(x)\in R_L(x)]\ge p(|x|)-ϵ(|x|)-negl(n)$$

可以证明 Blum’s Protocol 是一个 PoK 系统（构造提取器 $Ext(P^{\ast },G)$，通过 rewind 技术运行 expected poly-time 获得两个可接受副本 $(a,e,z),(a,e^{\prime },z^{\prime })$，其中 $e\ne e^{\prime }$，从而可以提取出汉密尔顿圈 $H\subseteq G$），因此

1. 如果 DL 假设成立， $n$-parallelized 版本的 Blum’s Protocol 是一个 $4$-round 的 perfect WI 的 argument of knowledge，其 knowledge error 为 $k.e.=negl(n)$
2. 如果 OWF 存在， $n$-parallelized 版本的 Blum’s Protocol 是一个 $4$-round 的 computational WI 的 proof of knowledge，其 knowledge error 为 $k.e.=negl(n)$
3. 如果 OWP 存在， $n$-parallelized 版本的 Blum’s Protocol 是一个 $3$-round 的 computational WI 的 proof of knowledge，其 knowledge error 为 $k.e.=negl(n)$

于是所有 $NP$ 语言都有这种 proof / argument of knowledge 系统。

Others

Public-coin

验证者发送的消息都是 random coins，因此 $V$ 可以不用看收到了什么消息，直接 “闭着眼睛” 抛币。直到交互结束后，$V$ 才对收到的 $Vie{w}_V$ 进行处理，决定是否 accept 这次的 proof。即 Public-coin 中的 $V$ 的唯一行为就是 “掷币并发送掷币结果”；对应的 Private-coin 是说，$V$ 的 coins 不被公开给 $P$，同时内部执行一定的计算，将计算结果发送给 $P$。

• 语言类 $NP$ 上的 $s.e.=negl(n)$ 的常数论 ZK 协议存在，但不是 public-coin 的
• Goldreich-Krawczyk black-box barrier：在 Black-box Simulators 下，如果语言 $L$ 有一个 $s.e.=negl(n)$ 的 $3$-round public-coin computational ZK proof 系统，那么 $L$ 仅存在于 $BPP$ 内（不是非凡断言）
• [Barak01] 给出了一个 $NP$ 上的 non-black-box 的具有 $s.e.=negl(n)$ 的常数轮 public-coin ZK argument 协议，同时它的模拟器是 strict poly-time 的（哇哦！同时突破了好多个 black-box barrier！但是后续人们似乎找不到更多或更一般的 non-black-box 构造？）
• $NP$ 上的 $3$-round public-coin ZK 协议似乎也不可能存在 [Canetti et al. 19]
• 注意，上述的 Black-box Barrier 是针对 “所有的 $NP$ 语言” 来说的。例如 Schnorr 协议是 Special HVZK 的（虽然无法在标准假设下证明它是 ZK / WH 的），经过 Fiat-Shamir Heuristic（它只要求原始协议的 HVZK 性质），得到的 Schnorr 签名在 RO 模型下是 ZK 的（在标准模型下，NIP 以及数字签名不是严格零知识的）

Publicly Verifiable

公开可验证，这主要是针对于 non-interactive proof / argument（NIP）来说的，每一个人都可以验证 $P$ 给出的 proof 是否正确。

1. 对于 traditional proof system，这就是一个公开可验证的证明，但同时每个人都获得了知识。
2. 对于 ZK IP system，由于 $Sim$ 可模拟出 $Vie{w}_V^P$，因此 $(P,V_1)$ 交互的视图，无法使得 $V_2\ne V_1$ 相信（信心来源于自己的随机性）。

Sigma-Protocol

$\Sigma$ 协议是一族 $3$-round public-coin proof/argument 系统，它满足 IP 的基本要求，同时有：

• Special Soundness：给定任意两个 accepting 副本 $(a,e,z),(a,e^{\prime },z^{\prime })$，其中 $e\ne e^{\prime }$，存在 PPT 抽取器 $Ext$，存在一个多项式 $poly(n)$，使
  $$Pr[Ext((a,e,z),(a,e^{\prime },z^{\prime }))\in R_L(x)]\ge \frac{1}{poly(n)}$$

  这是一个 strong 的安全性要求，它比 PoK 更强（PoK 可能需要多个 accepting 副本才能提取出知识）。可以证明，Special Soundness 直接导致了 PoK 以及 Soundness。

• Special Honest Verifier Zero Knowledge（SHVZK）：给定 random 挑战 $e$，存在 PPT 模拟器 $Sim$，使得
  { S i m V ( x , z ) } x ∈ L , z ∈ { 0 , 1 } ∗ ≡ { V i e w V ( z ) P ( w ) ( x ) } x ∈ L , z ∈ { 0 , 1 } ∗ \{Sim_{V}(x,z)\}_{x \in L,z \in \{0,1\}^*} \equiv \{View_{V(z)}^{P(w)}(x)\}_{x \in L,z \in \{0,1\}^*} {SimV​(x,z)}x∈L,z∈{0,1}∗​≡{ViewV(z)P(w)​(x)}x∈L,z∈{0,1}∗​

  这儿是 perfect indistinguishable，其中 $V$ 是 public-coin 的诚实证明者。实际上，这个 SHVZK 压根就不是一种安全性！不过，对于 Fiat-Shamir Transform 来说，这种很差的性质就足够了。

如果 OWP 存在， $n$-parallelized 版本的 3-round Blum’s Protocol 是一个 computational WI PoK 的 $\Sigma$-协议，其中 $k.e.=negl(n)$

Reduction / Simulation: Universal v.s. Individual

安全归约上的巨大鸿沟：

1. Universal Reduction/Simulation（$\exists \mathcal{R},\forall \mathcal{A}$）：这几乎是目前唯一已知的安全性归约 / 模拟技术，包括经典的黑盒归约和 Barak 的非黑盒模拟。然而，这个归约算法 $\mathcal{R}$ 被需要对所有的敌手都奏效，但它唯一被给定的仅仅是敌手 $\mathcal{A}$ 的描述（代码），要从这个 code 中提取出敌手的策略（包括随机性、计算的函数、函数的结构）这对于 PPT 能力的模拟器来说是无能为力的。

2. Individual Reduction/Simulation（$\forall \mathcal{A},\exists \mathcal{R}$）：在大多数的安全性定义中，只要求归约算法的存在性是合理的。毕竟安全性归约旨在给人们以信心，在实际中我们不需要用到归约算法。对于每一个 $\mathcal{A}$，它对应的 $\mathcal{R}$ 内部可以被嵌入 $\mathcal{A}$ 的策略，因此 Individual Reduction 的能力也许比 Universal Reduction 的能力强得多。