第二十三讲 零知识证明技术

1、第二十三讲 零知识证明技术 Peggy：“我知道联邦储备系统计算机的口令， McDonald的秘密调味汁的成分，以及Knuth第5卷 的内容。” Victor：“不，你不知道。” Peggy：“我知道。” Victor：“你不知道！” Peggy：“我确实知道！” Victor：“请你证明这一点！” Peggy：“好吧，我告诉你！”她悄悄地说出了口 令。 Victor： “太有趣了！现在我也知道了。我要告诉 华盛顿邮报。” 许多年前，有报道称小偷在一个超市中放 置假的ATM机。当人们将银行卡插入机器 并输入鉴别身份的秘密时，机器将这些信 息记录下来并反馈消息说机器不能接受这 种类型的银行卡。小

2、偷接下来就可以制造 假的银行卡，并使用得到的身份鉴别秘密 信息到真的ATM机上提取现金。 如何避免这一情况发生？在很多情况下需 要出示鉴别身份的秘密或口令来完成交易。 任何人在得到这个秘密再附加一些(几乎公 开的)身份信息之后，就可以冒充这个人。 我们需要解决的问题就是使用秘密但在使 用的过程中不留给攻击者任何可以重复使 用的信息。这就产生了零知识证明技术。 本讲提要 q 零知识证明概念总揽 q Fiat-Shamir鉴别协议 q Feige-Fiat-Shamir鉴别协议 q GQ鉴别协议 q Schnorr鉴别协议 1 零知识证明概念总揽 1.1 思想 1.1 思想(续) Peggy知道这

3、个洞穴的秘密。她想对Victor 证明这一点，但她不想泄露咒语。下面是 她如何使Victor相信的过程： (1) Victor站在A点。 (2) Peggy一直走进洞穴，到达点C或点D。 (3) 在Peggy消失在洞穴中之后，Victor 走 到点B。 1.1 思想(续) (4) Victor向Peggy喊，要她： (4.1) 从左通道出来，或者； (4.2) 从右通道出来. (5) Peggy答应了，如果有必要她就用咒语打 开密门。 (6) Peggy和Victor重复第(1)到第(5)步n次。 1.1思想(续) 评述评述. 协议使用的技术叫做分割选择技术(cut and choose)，因

4、为它类似如下将任何东西等分的 经典协议： (1) Peggy将东西切成两半。 (2) Victor给自己选择一半。 (3) Peggy拿走剩下的一半。 Peggy最关心的是第(1)步中的等分，因为 Victor可以在第(2)步选择他想要的那一半。 1.2 交互证明系统和零知识证明协议 零知识证明协议是交互证明系统的一个实 例，这里一个证明者和一个验证者交互多 轮。证明者的目标是让认证者相信声称的 正确性，例如，声称掌握一个秘密。验证 者要么接受证明要么拒绝证明。这与传统 的数学概念的证明有所不同，交互游戏的 证明是随机而不是绝对的。由于这个原因， 一个交互证明常常被称为协议证明。 1.2 交互

5、证明系统和零知识证明协议(续) 用于鉴别的交互证明可以被形式化为知识证 明。 证明者A掌握某个秘密s，并通过正确 的回答验证者B所提出的问题(涉及的是公开 已知的输入和协商一致的函数)使其相信确 实掌握秘密s，当然，回答这些问题需要秘 密s。注意证明掌握秘密s不同于证明s存在。 一个交互证明是知识证明如果证明满足完备 性和正确性属性。 1.2 交互证明系统和零知识证明协议(续) 定义定义1 (完备属性) 一个交互证明(协议)是完备 的，如果给定一个诚实的证明者和认证者， 协议就能以压倒的概率获得成功(也就是，验 证者接受证明者的宣称)。 评论评论. 完备性可以看作是协议在诚实的参与者 执行的情

6、况下的一般要求。对压倒的概率的 定义依赖具体应用，但通常隐含失败的概率 无实际意义。 1.2 交互证明系统和零知识证明协议(续) 定义定义2 (正确属性) 一个交互证明(协议)是正 确的，如果存在一个平均多项式时间算法 M满足如下性质：如果一个不诚实的证明 者(A)可以以不可忽略的概率成功的与B执 行协议，M则可以用来得到这个证明者的 知识(本质上等于A的秘密)，这将使得后续 的协议执行以压倒概率获得成功。 1.2 交互证明系统和零知识证明协议(续) 由于任何有能力冒充A的一方都等同于知道 A的秘密知识(M可以在多项式时间内来计算 它)，正确属性保证了协议确实提供了对知 识的证明知识等价于询问

7、的正确应答。正 确属性因此阻止了不诚实的证明者使诚实 的验证者相信知识的可能。 1.2 交互证明系统和零知识证明协议(续) 定义定义3 (零知识属性) 一个知识证明的协议 有零知识属性，如果协议可模拟如下功能： 存在一个平均多项式算法(模拟器)，它可 以不和真实的证明者交互就可以产生一些 证明必要的交互消息。这些消息副本与同 真实的证明者交互产生的结果不可区分。 1.2 交互证明系统和零知识证明协议(续) 评述评述. (1) 零知识属性表明一个证明者执行协议 (即使与恶意验证者交互)不会透露任何信 息 (即除了特定的声称正确以外的关于他 的秘密知识)，这无异于在多项式时间从 公开信息中计算。因

8、此，参与者不会增加 后续冒充成功的机会。 1.2 交互证明系统和零知识证明协议(续) (2) 考虑一个观查者C观测证明者A与验证者 B (B C)一个零知识证明协议交互过程，且 B确定了A掌握某个知识。向B证明的过程并 不能给C任何担保。(事实上，A和B可能事 先串通应答内容来欺骗 C。) 相似情况，记 录零知识证明协议的交互也不能进行回放。 这就是零知识属性的基本思想，即证明过 程可以由验证者单独模拟完成。 1.2 交互证明系统和零知识证明协议(续) (3) 零知识属性(定义定义3)不能保证协议是安 全的 (也就是，获得秘密知识的可能性可 以忽略)。同样，正确属性(定义定义2)也不能 保证协

9、议安全。这两个属性只有在攻击 者面临计算困难问题的时候才有意义。 1.3 零知识证明协议的一般结构 案。就限定了将来的可能答问题的集合，因此，也 回答在本次协议执行中所能随机性，并限定了 一个每一次协议执行的的公开证据。这提供了 承诺，并从中计算相关合上的元素做一个秘密 择一个在事先定义的集结构：证明者随机的选 交互零知识协议的一般以上描述了一大类三次 ： ： ： A BA BA BA 回答 提问 证据 1.3 零知识证明协议的一般结构(续) 的概率。 功制循环次数降低欺骗成果需要，就可以通过控 一个循环执行过程，如检查是否正确。协议是 做出回答，而，给接着选择一个问题提交 的秘密知识。帮助分

10、析回答一个问题，并不能 开证据提出的问题，而有能力回答所有根据公 才道秘密知识的合法根据协议设计，只有知 B AAB A A 1.4 零知识协议VS. 非对称协议 (1) 使用不退化：协议具有零知识属性因此不 会因为重复使用而降低安全性并可阻止选择 消息攻击。这可能是零知识技术在实践中最 吸引人之处。 (2) 无需加密：许多零知识技术都不需要使用 加密算法。 (3) 效率：虽然一些零知识基技术非常有效， 但是具有零知识属性的协议通常比没有零知 识属性的非对称协议需要更多通信和计算开 销。更为有效的实用零知识基方案通常源于 交互证明的特性，而不是它的零知识特性。 1.4 零知识协议VS. 非对称

11、协议(续) (4) 没有证明的假设：许多零知识协议 (“证 明知识”)本身依赖于和非对称技术一样的 未经证明的假设(例如，分解的困难)。 (5) 零知识基与零知识：虽然有着严谨的理 论支持，许多基于零知识概念的技术在实 践中缺少形式化的零知识和/或正确属性的 支撑，导致这一切的是出于效率或其它原 因的参数选择问题。事实上，许多这类概 念是渐进的，并不能直接应用到实用协议 中来。 2 Fiat-Shamir鉴别协议 。掌握秘密接受证明认为次都成功完成， 。如果连续且独立次如下的步骤循环执行协议执行 作为公开密钥。登记，并向计算 ，互素的秘密选择一个与每一个声称者 保密。和素数 ，但将型的模选择并

12、公布一个信任中心 一次性建立过程 。其掌握知识 证明次向验证者轮协议通过执行一个：证明者 鉴别协议 sAB tt vTn sv nssnA qp qpnT s BtA )( . (2) ) mod( 1 1 (1.2) RSA (1.1) . (1) 3 Shamir-Fiat 2 摘摘要要 协协议议1 1 2 Fiat-Shamir 鉴别协议(续) )0 0 ) (mod) (mod ( ) (mod 0 (2.4) 1) ( ) (mod 0) ( )( (2.3) 1 0 )( (2.2) ) (mod )( 1 1 )( (2.1) )(Shamir-Fiat 22 2 2 2 的情况

13、。是为了排除 。注意验证，由于 或者，得根据就可以接受证明。 了拒绝证明，否则，验证，如果 。如果者 或如果，回答计算并发送给 。给发送 并，或者比特问题随机的选择一个 。给证据发送 ，并且，承诺选择一个随机数 续鉴别协议 r ynsvnvxy xyenvx yBy ensry eryyBA Ae eeB Bnrx nrrA e 协协议议1 1 B A ) (mod 2 nrx ) (mod 0 2 证明。 拒绝接受证明；否则则 ，并如果 BB nvxyy e 1 0，e )(mod ns ry e 2 Fiat-Shamir 鉴别协议(续) 2 Fiat-Shamir鉴别协议(续) 的身份。

14、受回答正确的情况下才接 都轮个问题只有在全部次，协议需要执行 或例如，的小数值可能性到一个可以接受 为了减少欺骗的可能可以不被发现。问题，因此有 的一个他人只能至多回答其中回答两个问题，但是其 的证明者可以个知道是用来阻止欺骗的。一者而言 对诚实证明，另一个容易的问题她掌握的秘密知识 其中一个需要有能力回答两个问题，要求或测试 证明。提问做如下解释和非正式的可以对 A ttBt tt s s Ae t )( )40 = 20 = (2 1/2 ) ( )( 协议(1) 1 评评述述. . 2 Fiat-Shamir鉴别协议(续) 不能预测实时问题。 并，因为并不能冒充管可以模拟证明过程， 就是

15、零知识属性。尽产生的对不可区分，这 的概率分布实际上与，信息对的方法，但对 建立。虽然这并不是或定义 ，选择自己很好的模拟：随机好可以为验证者 恰，产生的信息对。由并不知道随机数 的信息，因为也没有提供任何关于 ，然而答案的秘密是独立于答案 BAB A yx Anv yyx yB yxArB sns r ysAry ) ( ) mod(/ ) ( ) mod( (2) )续( 22 评评述述. . 3 Feige-Fiat-Shamir鉴别协议 。，这里计算 的分解。否则将导致 可以得到保证，但是这一点几乎肯定，要求原因， 由于技术，个随机整数选择 做如下步骤每个实体每个实体秘密参数选择 为定

16、义的安全参数。和分解困难。整数，并且满足 向所有用户公开公共模信任中心系统参数选择 自己的身份。 证明轮协议向验证者次执行一个通过摘要：证明者 鉴别协议 kinsv n ns nssssk A tknqp nT BtA ii i ik 1 ) (mod (2.2) ) 1 )( ( 1 1 . . . (2.1) . . (2) . (1) 3 Shamir-Fiat-Feige 2 21 协协议议2 2 3 Feige-Fiat-Shamir鉴别协议(续) )0 ( 0 ) (mod (3.4) ) ( ) (mod )( (3.3) ) . . . ()( (3.2) )( )mod( 1

17、1 (3.1) ) . . . ( . (3) ) . . . ( ) . . . ( ) ( (2.3) )(Shamir-Fiat-Feige 1 2 1 21 2 21 21 21 的情况。者选择后一条是为了防止攻击 。和，并验证计算 。的乘积问中的 和定义在提：答案计算并发送给 。，比特向量一个提问发送给 。给证据发送 ，并并计算，选择一个随机整数 。；，的真实公开密钥知道轮都能成功。假定 的身份，如果全部将接受次。下面的步骤执行协议执行 程。这是一次性的建立过，密密钥 知道自己的秘的公开密钥，当然只有登记为；，将 就这样认证自己的身份，照片例如，通过非密码手段向 续鉴别协议 r zx

18、znvyzB s rnsryBA eeekAB Bx n rxnrrA nvvvABt ABt sss AAnvvv TTA k j e j j k j e j k k k k j j 协协议议2 2 3 Feige-Fiat-Shamir鉴别协议(续) A B ) (mod 2 nrx 拒绝证明。 否则，接受证明；则，并且 如果 B Bxz nvyz j j e e j ) 0(mod 1 2 1 0 ) . . . ( 1 ， ik eee ) (mod 1 nsry j e j 3 Feige-Fiat-Shamir鉴别协议(续) 。和因为 的身份，这是并接受计算 。数值计算并发送给 。

19、，比特向量一个发送给 。，并发送它给，计算选择 。，密钥是 ，秘密；，公开密钥是 。，和，计算 。，个随机整数选择 做如下步骤实体 被定义为安全参数。和。整数 ，并公布，选择素数信任中心 明选择小的参数以利于说 0 528015 ) (mod (3.4) 403104 ) mod ( (3.3) 1) 0 (0 3 (3.2) 528015 1279 (3.1) (3) 4646) 43215 (157 553913) 429490 338402 (112068 (2.3) 429490 338402 112068 (2.2) 4646 43215 1573 ) (2.1 . (2) 1 3

20、553913 811 683 (1) )( 3 2 3 321 321 zxz AnvyzB nsryBA AB BxrA vvv sss A tk qpnqpT 例例子子1 1 3 Feige-Fiat-Shamir鉴别协议(续) 。和 数知识证明，这里假定参况下是对知识的一个零 议在有可信服务器的情零知识和正确属性。协 的分解问题。算 。这个问题等价于计的模平方根的困难问题合数 赖于计算未知分解的大安全假设需求。安全依 的概率保证冒充成功。击也只有 是困难的，最好的攻分解安全的，也就是，如果 息攻击可以证明是抵抗选择消伪造概率。 )(log ) log O(log (3) (2) 2 协议

21、 (1) ntnk n n n tk 2 评评述述. . 3 Feige-Fiat-Shamir鉴别协议(续) 。意味着减少 作为常数，增加信开销。乘积行，可以减少计算和通 协议执全参数使得仅需要一轮安全平衡。通过平衡安 。，的安全：；，的安全：对于 参数选择，是适合的选择。具体的和通信的平衡， 算，存储，试已经足够。考虑到计用户防御冒充的鉴别测 对于个人万分之一，这在现实中冒充成功的概率只有百 就可以保证满足和数参数选择。选择安全参 tk tk tktk k tktk (5) 5 6 2 4 5 2 181 20 (4) )续( 3020 评评述述. . 3 Feige-Fiat-Shami

22、r鉴别协议(续) ，但并不增加轮数。伪造可以降低错误率行循环 相对于串执行在交互证明中这种并行这样做仍然是安全的。 条消息并行执行，轮的让全部协议的平行版本，可以 少。那么通信复杂度可以减的验证也做相应修改， ，而不是值一个比特例如，发送给如果 的模联系起来。需要将每个用户和他们 仍然自己的模，做改变，每个用户选择步的第 修改考虑。 )() ( 3 (6.3) )(Hash)128( (6.2) (1) (6.1) (6) )续( t B xxhBA T协协议议2 2 评评述述. . 3 Feige-Fiat-Shamir鉴别协议(续) 。并将其交给的平方根就可以计算 的分解，知道。由于信任中

23、心是一个适当的公开函数 计算出来，这里，用和其他实体可以由 ，的公开值。的信息或其它验证者希望验证 例如，名字，地址，的身份不同位串识每个实体 分配一个标份基方案。方案可以改造成如下身 Asv nT fiIfvBT kivA IA T ii Ai i A )( 1 ) ( (6.4) )续( 评评述述. . 3 Feige-Fiat-Shamir鉴别协议(续) 的离线攻击。须适当增加以防止对 的比特长度必方案，提问以变成一个非交互签名 交互鉴别方案就可。通过这一变换，一个者的作用 基本起到一个验证的一个连接与被签名消息据 代替，这里是证值用单向随机提问 者的数字签名方案：将验证顺序的鉴别协议转

24、变为 回答提问一个证据如下的一般方法可以将 Hash ) ( )|( Hash (6.5) )续( e hmx mxhee 评评述述. . 4 GQ鉴别协议 。并保证其真实性，统参数所有用户都可以获得系 。，并计算他的秘密指数 ，这里，满足定义一个公开指数 必定不可能。，分解作为。 并产生模和型素数选择一个秘密的随机绑定。 身份负责将公开密钥与用户一个为各方信任的权威 系统参数选择 。通过掌握知识份 证明自己的身轮协议向验证者通过一个摘要：证明者 鉴别协议 )( )( (1.3) ) (mod 1)1)( 1 )(3 (1.2) )RSA( RSA (1.1) . (1) )( 3 GQ 1

25、nv vsqp vvT nqp nqpT T s BA A 协协议议3 3 4 GQ鉴别协议(续) 接受其身份。次执行都成功的情况下仅在 证明自己的身份；次执行如下步骤向通过协议执行 。交给审定合格的数据将秘密 。，困难隐含了假定分解一个公开的冗余函数。 是，这里满足，冗余身份可以计算 ，从这个身份值被赋予唯一一个身份每个用户 每个用户参数选择 续鉴别协议 tB BtA AnJsT nJn fnJIfJ IA s AA A AAA A . (3) ) (mod)( )( (2.2) )1 )( ( 1 )( )( (2.1) . (2) )(GQ 协议3协议3 4 GQ鉴别协议(续) )0 (

26、 0 )(mod )( (3.5) )()(mod (3.4) 1 )( (3.3) ) ( (3.2) ) (mod )( 1 1 )( (3.1) )(GQ 。攻击者选择后一种情况是为了阻止身份的证明。 对其，就接受和，并且如果 ，计算建立从见上面之后，用收到 。回答给计算并发送 。，给，提问数选择并发送一个随机整 。给，发送整数对 。证据 ，并且计算，承诺选择一个随机整数 续鉴别协议 r AzxznyJ zJIfyB BnsryA AveeB BxIA nrx nrrA ve A AA e A A v 协议3协议3 4 GQ鉴别协议(续) B A ) (mod nrxI v A ， 拒绝

27、证明。否则， 接受证明；则并且 如果 B Bxz nyJz ve A , ) 0(mod vee1 ，这里 ) (mod nsry e A 4 GQ鉴别协议(续) 。和 的身份，这是因为并接受计算 。给发送 。给发送随机提问 。给，发送整数对 。并计算选择 。发给将审定合格的数据 。的冗余身份参数是假定 让全体用户得到。，系统参数 。 ，并且计算，选择计算 。，并且计算，选择素数权威 使用小参数并且 0 89525 )(mod (3.5) 83551 ) (mod (3.4) 38980 (3.3) 89525) ( (3.2) 89525 ) (mod 65446 (3.1) (3) 403

28、154 ) (mod )( (2.2) 34579 (2.1) (2) 420491) (54955 (1.3) 233875 mod 54955 419184 1)1)( (1.2) 420491 739 569 (1.1) (1) 1) ( 1 zxz AnyJz B BnsryA AeB BIA nrxrA AnJsT JA vs vqpT qpnqpT t ve A e A A v s AA A 例例子子2 2 4 GQ鉴别协议(续) 是困难的。的因子情况下通常认为知道 更困难，但在不这并不比分解是攻击协议的方法；问题解 也就是，求次平方根的模合整数需要的安全假设。计算 者存在的环境而

29、定。比特长度应该根据攻击 的攻击协议。推荐的计算并进一步像验证者一样 的概率成功事先猜测证明者可以有效计算。一个冒充的 有利于一些值如；却需要许多轮交互协议，这里 比较决定安全等级，中伪造的概率。在 评述 n n vn vyJx ev vv v ve A )RSA ( (2) )( / 1 12 )2 Shamir-Fiat( 协议 (1) 16 3 . 4 GQ鉴别协议(续) 误审定合格的数据。 假身份的错止攻击者计算出对应虚使用冗余函数的目是阻 的多项式。必须不大于为常数的情况，对于 的渐进上限：是一个整数，考虑，这里要求 方案的零知识属性对于相反，零知识属性。与正确性 。必须渐进增加快于

30、要求是，技术上对于正确属性的 是一个常数，。如果，伪造的概率是，对于一般参数 比特素数。是一个而方案建议正确属性。在实践中， 评述 (5) log ) O(log GQ (4) loglog )( 1 GQ (3) )续( ntv t cnvt nt vvtvn kvt c t . 5 Schnorr身份鉴别 关联得到。与秘密知识钥 密通过认证证书将其公开，鉴别不给出知识 来证明其掌握秘密根据一个提问个时变的方式 以一。基本思想是证明者也使得交互的数据减少 。当然，使用这种群的乘法群，这里阶为 的改进源于使用整数模进一步重要的计算效率 。者计算能力有限的情况开销，这非常适合证明 算算以减少证明

31、者实时计难性。设计允许预先计 离散对数问题的困鉴别协议的安全性依赖 av Aaa e A pqq p )( )( 1)( | Schnorr 5 Schnorr身份鉴别(续) ) Hash()( )( (1.3) 1 1 (1.2) )( 1 (1.1) . (1) 3 Schnorr 。数和任意一个签名机制 函适当的公开涉及在签名之前的一个。签名 的对消息，它可以验证的验证公开密钥的函数中心 和信任，系统参数每一方得到一份真实的 。，的元选择一个乘法阶为 可能。的离散对数在计算上不保证模整除。 可以被另一个素数满足选择一个适当的素数 系统参数选择 身份。 证明自己的轮协议向验证者通过一个摘要

32、：证明者 鉴别协议 TT SmS mTT qp pq pq pp BA 协议4协议4 5 Schnorr身份鉴别(续) 绑定。和将，书 颁发的证，最后得到一个由传递给份，接着将真实的 验证自己的身例如，出示护照通过传统方式向 。 ，并计算，选择一个秘密密钥 。选择一个唯一身份每个实体 每个用户参数选择 。全等级 定义一个安，例如，选择一个安全参数 续鉴别协议 vIvISvIcert TTv TA p vqaaA IA qtt AATAA a A t t )( ( )( (2.3) ) (mod 1 0 (2.2) (2.1) . (2) )2 ( 2 40) ( (1.4) )(Schnorr 协议4协议4 5 Schnorr身份鉴别(续) 的身份。，接受，如果计算 。给回答并发送检查 。，给 ，提问随机数从未使用过的实性，接着发送一个 的真的公开密钥中的签名验证在证书通过 。给，并发送 证据计算，承诺选择一个随机数 验证自己的身份。按如下步骤向协议执行 续鉴别协议 AxzpvzB BqreayeA A ee vAcertTB Bxcertpx qrrA BA ey t t A A r ) (mod (