您现在的位置是:首页 >技术交流 >零知识证明:安全定义网站首页技术交流

零知识证明:安全定义

山登绝顶我为峰 3(^v^)3 2024-06-17 10:13:30
简介零知识证明:安全定义

之前在本科的课程仅仅略微介绍了下零知识证明,之后自学了一些相关内容,但不成体系。本学期跟着邓老师较为系统地学习了 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 T T 的一个证明(Proof) w w w(实际上是一个证据 witness),可以被一个 PPT 的图灵机 M M M 判定:
M ( T , w ) = 1    ⟺    T  is true M(T,w) = 1 iff T ext{ is true} M(T,w)=1T is true

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

由于 L ⊆ N P L subseteq NP LNP,那么存在 PPT 的关系 R L R_L RL,使得
∀ x , ∃ y , ∣ y ∣ ≤ p o l y ( ∣ x ∣ ) , R L ( x , y ) = 1 forall x,exists y,|y| le poly(|x|),R_L(x,y)=1 x,y,ypoly(x),RL(x,y)=1

因此语言 L L L 存在证明系统 ⟨ P , V ⟩ lang P,V ang P,V,无界的 P P P 找出证据 w w w,PPT 的 V V V 执行 R L R_L RL 进行判断。即 L ⊆ N P L subseteq NP LNP 当仅当 L L L 有一个证明系统。

然而,传统的数学证明系统有些限制:proof 必须是短的,且 V V 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 V 没能力计算的,如果 V V V 本身就有能力给出 witness,那么这种交互证明是没有任何意义的。

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

  • V V V 是 PPT 能力的

  • 完备性:对于任意的 x ∈ L x in L xL,都有
    P r [ ( P , V ) ( x ) = 1 ] ≥ c ( n ) Pr[(P,V)(x) = 1] ge c(n) Pr[(P,V)(x)=1]c(n)

  • 可靠性:对于任意的 x ∉ L x otin L x/L,任意的(无界)敌手 P ∗ P^* P,都有
    P r [ ( P ∗ , V ) ( x ) = 1 ] ≤ s ( n ) Pr[(P^*,V)(x) = 1] le s(n) Pr[(P,V)(x)=1]s(n)

    这里的 s ( n ) s(n) s(n) 叫做 Soundness Error,我们要求 c ( n ) − s ( n ) > 1 p o l y ( n ) c(n) - s(n) > dfrac{1}{poly(n)} c(n)s(n)>poly(n)1,类似于 BPP 的概率放大,这等价于 c ( n ) = 1 − n e g l ( n ) c(n)=1-negl(n) c(n)=1negl(n) s ( n ) = n e g l ( n ) s(n)=negl(n) s(n)=negl(n)

  • P ∗ P^* P 是 PPT 能力的非一致(non-uniform)敌手,如果对于充分长的 x ∉ L x otin L x/L 此协议满足 soundness,我们称这个系统是 Interactive Argument(交互式论证)

Power of IP

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

由于传统数学证明系统属于 I P IP IP 类,因此它包含 N P NP NP。事实上, P S P A C E = I P PSPACE = IP PSPACE=IP N P , c o - N P ⊆ P S P A C E NP,co ext{-}NP subseteq PSPACE NP,co-NPPSPACE),它的能力比传统数学证明系统强的多(大多数人都认为 P ≠ N P ≠ P S P A C E ≠ E X P S P A C E P eq NP eq PSPACE eq EXPSPACE P=NP=PSPACE=EXPSPACE)。

例如,传统数学证明系统没办法有效的证明 “定理 A 没有短证明”,因为这需要穷举所有的短字符串,并依次验证它们都不是定理 A 的正确证明。一个 statement 的 witness 可能会很长(在 N P NP NP 之外),但是 IP 系统中的无界证明者 P P P,依然可以为 PPT 的验证者,提供一个短的 proof 使之相信它。例如下面的两个 c o - N P co ext{-}NP co-NP 类中的语言,
G N I : = { ( G 0 , G 1 ) : ∀ ϕ , ϕ ( G 0 ) ≠ G 1 } Q N R : = { ( x , n ) : ∀ w , x ≠ w 2 ( m o d n ) } GNI:={(G_0,G_1): forall phi,phi(G_0) eq G_1}\ QNR:={(x,n): forall w, x eq w^2 pmod n} GNI:={(G0,G1):ϕ,ϕ(G0)=G1}QNR:={(x,n):w,x=w2(modn)}

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

在这里插入图片描述

但是,实际上 Q N R ⊆ N P ∩ c o - N P QNR subseteq NP cap co ext{-}NP QNRNPco-NP,因此它本身就存在短证明(找出 n n n 的所有素因子,验证 x ( m o d p i ) ∈ Q N R , ∀ p i xpmod{p_i} in QNR, forall p_i x(modpi)QNR,pi)。另外,虽然没有人能证明 G N I ⊆ N P GNI subseteq NP GNINP,但是由于 G I GI GI 存在亚指数的算法 [Babai17],因此人们更愿意相信 G I GI GI 属于 P P P 类,此时 G N I GNI GNI 也自然会属于 P ⊆ N P P subseteq NP PNP。所以,上述的两个例子似乎并没有那么令人吃惊。

[Fortnow, Sipser, 88] 证明了,对于 c o - N P C co ext{-}NPC co-NPC 语言
c o - S A T : = { CNF  ϕ : ∀ x i ∈ { 0 , 1 } , ϕ ( x 1 , ⋯   , x n ) = 0 } co ext{-}SAT := { ext{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] 就考虑 P S P A C E - c o m p l e t e PSPACE ext{-}complete PSPACE-complete 语言
{ CNF  ϕ : ∃ x 1 , ∀ x 2 , ⋯   , Q n x n ∈ { 0 , 1 } , ϕ ( x 1 , ⋯   , x n ) = 1 } { ext{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,,Qnxn{0,1},ϕ(x1,,xn)=1}

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

在这里插入图片描述

Zero Knowledge

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

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

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

我们说一个关于语言 L L L 的 IP 系统 ( P , V ) (P,V) (P,V)零知识性,对于任意的 non-uniform PPT 敌手 V ∗ V^* V,都存在一个 non-uniform PPT 模拟器(simulator) S i m Sim 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)}xL,z{0,1}c{ViewV(z)P(w)(x)}xL,z{0,1}

其中 z z zauxiliary input(甚至可以是 witness),用于 ZKP 作为子协议嵌入到其他协议中时的归约使用(从协议执行中已经获得了一部分信息,这些信息不再被保护)。对于充分长的 x ∈ L x in L xL,任意的 non-uniform PPT 区分器 D D D,都有
P r [ D ( S i m V ∗ ( z ) ( x ) ) = 1 ] − P r [ D ( V i e w V ∗ ( z ) P ( w ) ( x ) ) = 1 ] ≤ n e g l ( n ) Pr[D(Sim_{V^*(z)}(x))=1] - Pr[D(View_{V^*(z)}^{P(w)}(x))=1] le negl(n) Pr[D(SimV(z)(x))=1]Pr[D(ViewV(z)P(w)(x))=1]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 ext{ 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 ∉ L x otin L x/L,(类)承诺协议有 perfect binding
  • 对于 ture 实例 x ∈ L x in L xL,(类)承诺协议有 perfect hiding

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

在这里插入图片描述
在这里插入图片描述

可以证明 P ⊆ P Z K P subseteq PZK PPZK(不必交互,自然完美)以及 G I , Q R ⊆ P Z K GI,QR subseteq PZK GI,QRPZK(可以构造出它们的 PZK IP 协议),但是 [Fornow88] 证明 N P C NPC NPC 极不可能属于 P Z K PZK PZK,因此 P Z K PZK PZK 语言类很小。

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

在这里插入图片描述

Randomness

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

  • 如果语言 L L L 拥有 computational ZK proof,其中的验证者 V V V 是确定性的,那么 L ⊆ R P L subseteq RP LRP 是 trivial 的。
  • 如果语言 L L L 拥有 computational ZK proof,其中的证明者 P P P 是确定性的,那么 L ⊆ B P P L subseteq BPP LBPP 是 trivial 的。

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

Expected Poly-time

在证明 ZK 性质时,持有 V ∗ V^* V 描述的模拟器 S i m Sim Sim V ∗ V^* V 提供随机带 r V r_V rV 使之运行(以 Black-box 方式),并为它模拟与 P P P 的交互过程(不持有 w w w S i m Sim Sim 如同 P P P 一样工作),从而构造出与 V i e w V ∗ ( z ) P ( x ) View_{V^*(z)}^{P(x)} ViewV(z)P(x) 不可区分的模拟视图。

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

在这种 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 的模拟器,归约过程中的重中之重,就是证明 S i m Sim Sim 的期望运行时间是多项式(或者说,证明 S i m Sim Sim 猜对的概率 p p p 是显著的,从而根据帕斯卡分布的期望, E ( t i m e ) = r = 1 p mathbb E(time) = dfrac{r=1}{p} E(time)=pr=1 是个多项式)。

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 假设成立,则任意的 N P NP NP 语言都存在 4-round 的 perfect ZK argument,其 soundness error 为 s . e . ≤ 1 2 + n e g l ( n ) s.e. le dfrac{1}{2}+negl(n) s.e.21+negl(n)
  2. 如果 OWF 存在,则任意的 N P NP NP 语言都存在 4-round 的 computational ZK proof,其 soundness error 为 s . e . ≤ 1 2 + n e g l ( n ) s.e. le dfrac{1}{2}+negl(n) s.e.21+negl(n)
  3. 如果 OWP 存在,则任意的 N P NP NP 语言都存在 3-round 的 computational ZK proof,其 soundness error 为 s . e . ≤ 1 2 + n e g l ( n ) s.e. le dfrac{1}{2}+negl(n) s.e.21+negl(n)

WI

为了把 soundness error 降低到 n e g l ( n ) negl(n) negl(n),需要多次独立执行(使用独立的随机带)IP 协议:重复 n n n 次可以降低到 1 / 2 n 1/2^n 1/2n,重复 log ⁡ 2 n log^2 n log2n 可以降低到 1 / n log ⁡ n 1/n^{log n} 1/nlogn。在协议的 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 ∨ L L^2 := L vee L L2:=LL 的 WI Proof 也是 WH 的。

我们说一个语言 L L L 的交互式 proof / argument 系统 ( P , V ) (P,V) (P,V)证据不可区分的WI),如果对于任意的 non-uniform PPT 敌手 V ∗ V^* V,任意的序列 { ( x , w 0 , w 1 ) : ( x , w 0 ) , ( x , w 1 ) ∈ R L } x ∈ L {(x,w_0,w_1): (x,w_0),(x,w_1) in R_L}_{x in L} {(x,w0,w1):(x,w0),(x,w1)RL}xL,都有
{ 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)}xLc{ViewV(z)P(w1)(x)}xL
对于只有一个 witness 的声明 x ∈ L x in L xL,上述定义是 trivial 的。WI 对于 composition 有着良好的兼容性:

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

WH

对于语言 L ⊆ N P L subseteq NP LNP,我们说分布簇 { X n  over  { x ∈ L : ∣ x ∣ = n } } n ∈ N {X_n ext{ over }{x in L:|x|=n}}_{n in mathbb N} {Xn over {xL:x=n}}nN 是关于 R L R_L RL 困难的(distribution of hard instances,原始论文中称之为 invulnerable generator),如果任意的 non-uniform PPT 敌手 M M M,都有
P r [ x ← X n : M ( x ) ∈ R L ( x ) ] ≤ n e g l ( n ) Pr[x leftarrow X_n:M(x) in R_L(x)] le negl(n) Pr[xXn:M(x)RL(x)]negl(n)

我们说一个语言 L L L 的交互式 proof / argument 系统 ( P , V ) (P,V) (P,V) 是关于分布簇 { ( X n , W n )  over  R L } n ∈ N {(X_n,W_n) ext{ over }R_L}_{n in mathbb N} {(Xn,Wn) over RL}nN 证据隐藏的WH),如果对于任意的 non-uniform PPT 敌手 V ∗ V^* V,都有
P r [ ⟨ P ( W n ) , V ∗ ( z ) ⟩ ( X n ) ∈ R L ( X n ) ] ≤ n e g l ( n ) Pr[langle P(W_n),V^*(z) angle(X_n) in R_L(X_n)] le negl(n) Pr[⟨P(Wn),V(z)⟩(Xn)RL(Xn)]negl(n)

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

  1. WH 的定义是依赖于分布簇 X n X_n Xn 的,对于同一个 n n n 敌手的 auxiliary input 是相同的(而在 ZK 定义中 z z z 可以依赖于 x x x)。即使 P P P 公开了无限多的 x ∗ ∈ L x^* in L xL 对应的 witness,只要这些 x ∗ ← X n x^* leftarrow X_n xXn 被采样的概率可忽略,那么 IP 系统依然是 WH 的。
  2. WH 仅仅确保 “whole” witness 不被泄露(类似于 OWF 和 hardcore 的关系),它允许泄露证据的部分信息(而 ZK 保证不泄露 witness 的任何信息)。这对于数字签名来说是个优势,因为数字签名不可以是 ZK 的(这就使得 S i m Sim Sim 伪造出签名),但是数字签名可以是 WH 的(只隐藏那些允许真实签名者可以正确签名的信息)(博主我还是不理解 ╥﹏╥)

L ⊆ N P L subseteq NP LNP,对应的关系为 R L R_L RL,定义
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=LL:={(x0,x1):i{0,1},xiL}RL2:={((x0,x1),w):i{0,1},(xi,w)RL}

我们用语言 L L L 上的 invulnerable generator 独立地采样两个困难实例 ( x 0 , w 0 ) , ( x 1 , w 1 ) ∈ R L (x_0,w_0),(x_1,w_1) in R_L (x0,w0),(x1,w1)RL,然后随机丢弃一个证据,就构造出了语言 L 2 L^2 L2 的一个困难实例 ( ( x 0 , x 1 ) , w b ) ((x_0,x_1),w_b) ((x0,x1),wb)

那么假如 ( P , V ) (P,V) (P,V) 是关于 L 2 L^2 L2 语言的 WI 系统,那么 ( P , V ) (P,V) (P,V) 也是关于 R L 2 R_{L^2} RL2hard distribution(其中的 x 0 , x 1 x_0,x_1 x0,x1 独立随机)的 WH 系统。归约过程中,假设与 P ( w b ) P(w_b) P(wb) 交互后 V ∗ V^* V 成功时总是输出 w b w_b wb,那么这就打破了 WI;假设与 P ( w b ) P(w_b) P(wb) 交互后 V ∗ V^* V 成功的条件下以显著占比输出 w 1 − b w_{1-b} w1b,那么这就打破了 hard distribution(交互过程中根本就没有 w 1 − b w_{1-b} w1b 的信息)。

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 L L 的 IP 系统 ( P , V ) (P,V) (P,V)proof(argument) of knowledge with knowledge error ϵ ( ⋅ ) epsilon(cdot) ϵ(),如果对于任意(充分长)的 x ∈ L x in L xL,任意的无界(PPT)敌手 P ∗ P^* P,假如
P r [ ⟨ P ∗ , V ⟩ ( x ) = 1 ] ≥ p ( ∣ x ∣ ) > ϵ ( ∣ x ∣ ) Pr[langle P^*,V angle(x)=1] ge p(|x|) > epsilon(|x|) Pr[⟨P,V(x)=1]p(x)>ϵ(x)

那么就存在一个 non-uniform PPT 提取器(Extractor) E x t Ext Ext,使得
P r [ E x t P ∗ ( x ) ∈ R L ( x ) ] ≥ p ( ∣ x ∣ ) − ϵ ( ∣ x ∣ ) − n e g l ( n ) Pr[Ext^{P^*}(x) in R_L(x)] ge p(|x|) - epsilon(|x|) - negl(n) Pr[ExtP(x)RL(x)]p(x)ϵ(x)negl(n)

可以证明 Blum’s Protocol 是一个 PoK 系统(构造提取器 E x t ( P ∗ , G ) Ext(P^*,G) Ext(P,G),通过 rewind 技术运行 expected poly-time 获得两个可接受副本 ( a , e , z ) , ( a , e ′ , z ′ ) (a,e,z),(a,e',z') (a,e,z),(a,e,z),其中 e ≠ e ′ e eq e' e=e,从而可以提取出汉密尔顿圈 H ⊆ G H subseteq G HG),因此

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

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

Others

Public-coin

验证者发送的消息都是 random coins,因此 V V V 可以不用看收到了什么消息,直接 “闭着眼睛” 抛币。直到交互结束后, V V V 才对收到的 V i e w V View_V ViewV 进行处理,决定是否 accept 这次的 proof。

  • 语言类 N P NP NP 上的 s . e . = n e g l ( n ) s.e.=negl(n) s.e.=negl(n) 的常数论 ZK 协议存在,但不是 public-coin 的
  • Goldreich-Krawczyk black-box barrier:在 Black-box Simulators 下,如果语言 L L L 有一个 s . e . = n e g l ( n ) s.e.=negl(n) s.e.=negl(n) 3 3 3-round computational ZK proof 系统,那么 L L L 仅存在于 B P P BPP BPP 内(不是非凡断言)
    1. negligible soundness error 以及 constant-round ZK 在黑盒模拟下不存在
    2. negligible soundness error 以及 public-coin 在黑盒模拟下不存在
  • [Barak01] 给出了一个 N P NP NP 上的 non-black-box 的具有 s . e . = n e g l ( n ) s.e.=negl(n) s.e.=negl(n)常数轮 public-coin ZK argument 协议,同时它的模拟器是 strict poly-time 的(哇哦!同时突破了好多个 black-box barrier!但是后续人们似乎找不到更多或更一般的 non-black-box 构造?)
  • 即使是 non-black-box 的, N P NP NP 上的 3 3 3-round public-coin ZK 协议似乎也不可能存在 [Canetti et al. 19]

Publicly Verifiable

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

  1. 对于 traditional proof system,这就是一个公开可验证的证明,但同时每个人都获得了知识。
  2. 对于 ZK IP system,由于 S i m Sim Sim 可模拟出 V i e w V P View_V^P ViewVP,因此 ( P , V 1 ) (P,V_1) (P,V1) 交互的视图,无法使得 V 2 ≠ V 1 V_2 eq V_1 V2=V1 相信(信心来源于自己的随机性)。

Sigma-Protocol

Σ Sigma Σ 协议是一族 3 3 3-round public-coin proof/argument 系统,它满足

  • Special Soundness:给定任意两个 accepting 副本 ( a , e , z ) , ( a , e ′ , z ′ ) (a,e,z),(a,e',z') (a,e,z),(a,e,z),其中 e ≠ e ′ e eq e' e=e,存在 PPT 抽取器 E x t Ext Ext,存在一个多项式 p o l y ( n ) poly(n) poly(n),使
    P r [ E x t ( ( a , e , z ) , ( a , e ′ , z ′ ) ) ∈ R L ( x ) ] ≥ 1 p o l y ( n ) Pr[Ext((a,e,z),(a,e',z')) in R_L(x)] ge dfrac{1}{poly(n)} Pr[Ext((a,e,z),(a,e,z))RL(x)]poly(n)1

    这是一个 strong 安全性要求,比 PoK 更强(PoK 可能需要多个 accepting 副本才能提取出知识)。

  • Special Honest Verifier Zero Knowledge(SHVZK):给定 random 挑战 e e e,存在 PPT 模拟器 S i m Sim 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)}xL,z{0,1}{ViewV(z)P(w)(x)}xL,z{0,1}

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

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

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。