《5零知识证明.pptVIP

零知识证明的概念 设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。 某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。 如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作零知识协议。 零知识证明的概念 在最小泄露协议中满足下述两个性质： (1) P无法欺骗V。换言之，若P不知道一个定理的证明方法，则P使V相信他会证明定理的概率很低。（正确性） (2) V无法欺骗P。换言之，若P知道一个定理的证明方法，则P使V以绝对优势的概率相信他能证明。（完备性） 在零知识协议中，除满足上述两个条件以外，还满足下述性质： (3) V无法获取任何额外的知识。（零知识性） 零知识洞穴 设P知道咒语，可打开C和D之间的秘密门，不知道者则走向死胡同。现在来看P如何向V出示证明使其相信他知道这个秘密，但又不告诉V有关咒语。 协议1：洞穴协议 V站在A点； P进入任一点C或D； 当P进洞之后，V走向B点； V叫P：(a)从左边出来，或(b)从右边出来 P按照要求实现（有咒语）； P和V重复执行(1)~(5)共n次。 零知识洞穴 若P不知道咒语，则在B点，只有50%的机会猜中V的要求，协议执行n次，则只有2? n次机会完全猜中。此洞穴问题可以转化为数学问题，P知道解决某个难题的秘密信息，而V通过与P交互作用验证其真伪。 平方根问题的零知识 令N = P Q，P、Q为两个大素数，Y是mod N的一个平方，且gcd(Y, N) = 1，注意找到mod N的平方根与分解N等价。 Peggy声称他知道Y的一个平方根S，但他不愿意泄露S，Vector想证明Peggy是否真的知道。下面给出了这个问题的一个解决方案。 Peggy选择两个随机数R1和R2，满足gcd(R1, N ) = 1，R2 = S R1–1，R1 R2 = S (mod N )。Peggy计算X1 = R12 (mod N)，X2 = R22 (mod N)，并将X1、X2发送给Vector。 Vector检验X1 X2 = Y (mod N)，然后Vector随机选择X1（或X2）让Peggy提供它的一个平方根，并检验Peggy是否提供的是真的平方根。 重复上面的过程直至Vector相信。 这里，Peggy不知道Y的平方根，虽然他可能知道X1、X2的一个平方根，但不是全部。 离散对数问题的零知识证明 Peggy试图向Vector证明他知道离散对数x，x = loggY mod p，Y = gx mod p 证明ElGamal解密的正确性 比如，Peggy试图证明他的ElGamal解密是正确的。 明文是m而不泄露他的私钥x。 Peggy的私钥为Y = gx mod p； ElGamal加密为m ? (U, V)， ElGamal解密为V / Ux ? m Peggy只需证明下面的两个离散对数相等即可：Y = gx，V / m = Ux，logg Y = logU (V / m)。 身份鉴别方案 在一个安全的身份认证协议中，我们希望被认证者P能向验证者V电子地证明他的身份，而又不向P泄露他的认证信息 Feige-Fiat-Shamir身份鉴别方案 Guillo-Quisquater身份鉴别方案 Schnorr身份鉴别方案 简化的Feige-Fiat-Shamir身份鉴别方案 可信赖仲裁方选定一个随机模数n = p1 × p2，p1、p2为两个大素数。实际中n至少为512比特，尽量长达1024比特。仲裁方可实施公钥和私钥的分配。他产生随机数v（v为对模n的二次剩余）。 换言之，选择v使得x2 = v mod n有一个解并且v–1 mod n 存在。以v作为被验证方的公钥，而后计算最小的整数s：s ≡ sqrt (v –1) mod n，将它作为被验方P的私人密钥而分发给他。 简化的Feige-Fiat-Shamir身份鉴别方案 实施身份证明的协议如下： (1) 用户P取随机数r（r m），计算x = (x2) mod n，送给验证方V： (2) V将随机比特b送给P； (3) 若b = 0，则P将r送给V；若b = 1，则将y = r s mod n送给V； (4) 若b = 0，则V验证x = r2 mod n，从而证明P知道sqrt(x)；若b = 1，则V验证x = y2 v mod n，从而证明P知道s。 这是一轮认证，P和V可将此协议重复t次，直到V确信P知道s为止。 简化的Feige-Fiat-Shamir身份鉴别方案 安全性讨论如下： P欺骗V的可能性。P不知道s，他也可选取随机数r，将x = r 2