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知道这个洞穴的秘密。她想对Victor证明这一点，但她不
3、想泄露咒语。下面是她如何使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)，因为它类似如下将任何东西等分的经典协议： (1) Peggy
4、将东西切成两半。 (2) Victor给自己选择一半。 (3) Peggy拿走剩下的一半。 Peggy最关心的是第(1)步中的等分，因为Victor可以在第(2)步选择他想要的那一半。 1.2 交互证明系统和零知识证明协议 零知识证明协议是交互证明系统的一个实例，这里一个证明者和一个验证者交互多轮。证明者的目标是让认证者相信声称的正确性，例如，声称掌握一个秘密。验证者要么接受证明要么拒绝证明。这与传统的数学概念的证明有所不同，交互游戏的证明是随机而不是绝对的。由于这个原因，一个交互证明常常被称为协议证明。 1.2 交互证明系统和零知识证明协议(续) 用于鉴别的交互证明可以被形式化为知识证明。
5、证明者A掌握某个秘密s，并通过正确的回答验证者B所提出的问题(涉及的是公开已知的输入和协商一致的函数)使其相信确实掌握秘密s，当然，回答这些问题需要秘密s。注意证明掌握秘密s不同于证明s存在。一个交互证明是知识证明如果证明满足完备性和正确性属性。 1.2 交互证明系统和零知识证明协议(续) 定义定义1 (完备属性) 一个交互证明(协议)是完备的，如果给定一个诚实的证明者和认证者，协议就能以压倒的概率获得成功(也就是，验证者接受证明者的宣称)。 评论评论. 完备性可以看作是协议在诚实的参与者执行的情况下的一般要求。对压倒的概率的定义依赖具体应用，但通常隐含失败的概率无实际意义。 1.2 交互证明
6、系统和零知识证明协议(续) 定义定义2 (正确属性) 一个交互证明(协议)是正确的，如果存在一个平均多项式时间算法M满足如下性质：如果一个不诚实的证明者(A)可以以不可忽略的概率成功的与B执行协议，M则可以用来得到这个证明者的知识(本质上等于A的秘密)，这将使得后续的协议执行以压倒概率获得成功。 1.2 交互证明系统和零知识证明协议(续) 由于任何有能力冒充A的一方都等同于知道A的秘密知识(M可以在多项式时间内来计算它)，正确属性保证了协议确实提供了对知识的证明知识等价于询问的正确应答。正确属性因此阻止了不诚实的证明者使诚实的验证者相信知识的可能。 1.2 交互证明系统和零知识证明协议(续)
7、定义定义3 (零知识属性) 一个知识证明的协议有零知识属性，如果协议可模拟如下功能：存在一个平均多项式算法(模拟器)，它可以不和真实的证明者交互就可以产生一些证明必要的交互消息。这些消息副本与同真实的证明者交互产生的结果不可区分。 1.2 交互证明系统和零知识证明协议(续) 评述评述. (1) 零知识属性表明一个证明者执行协议(即使与恶意验证者交互)不会透露任何信息 (即除了特定的声称正确以外的关于他的秘密知识)，这无异于在多项式时间从公开信息中计算。因此，参与者不会增加后续冒充成功的机会。 1.2 交互证明系统和零知识证明协议(续) (2) 考虑一个观查者C观测证明者A与验证者B (B C)
8、一个零知识证明协议交互过程，且B确定了A掌握某个知识。向B证明的过程并不能给C任何担保。(事实上，A和B可能事先串通应答内容来欺骗 C。) 相似情况，记录零知识证明协议的交互也不能进行回放。这就是零知识属性的基本思想，即证明过程可以由验证者单独模拟完成。 1.2 交互证明系统和零知识证明协议(续) (3) 零知识属性(定义定义3)不能保证协议是安全的 (也就是，获得秘密知识的可能性可以忽略)。同样，正确属性(定义定义2)也不能保证协议安全。这两个属性只有在攻击者面临计算困难问题的时候才有意义。1.3 零知识证明协议的一般结构案。就限定了将来的可能答问题的集合，因此，也回答在本次协议执行中所能随
9、机性，并限定了一个每一次协议执行的的公开证据。这提供了承诺，并从中计算相关合上的元素做一个秘密择一个在事先定义的集结构：证明者随机的选交互零知识协议的一般以上描述了一大类三次：ABABABA回答提问 证据1.3 零知识证明协议的一般结构(续)的概率。功制循环次数降低欺骗成果需要，就可以通过控一个循环执行过程，如检查是否正确。协议是做出回答，而，给接着选择一个问题提交的秘密知识。帮助分析回答一个问题，并不能开证据提出的问题，而有能力回答所有根据公才道秘密知识的合法根据协议设计，只有知BAABAA 1.4 零知识协议VS. 非对称协议 (1) 使用不退化：协议具有零知识属性因此不会因为重复使用而降
10、低安全性并可阻止选择消息攻击。这可能是零知识技术在实践中最吸引人之处。 (2) 无需加密：许多零知识技术都不需要使用加密算法。 (3) 效率：虽然一些零知识基技术非常有效，但是具有零知识属性的协议通常比没有零知识属性的非对称协议需要更多通信和计算开销。更为有效的实用零知识基方案通常源于交互证明的特性，而不是它的零知识特性。 1.4 零知识协议VS. 非对称协议(续) (4) 没有证明的假设：许多零知识协议 (“证明知识”)本身依赖于和非对称技术一样的未经证明的假设(例如，分解的困难)。 (5) 零知识基与零知识：虽然有着严谨的理论支持，许多基于零知识概念的技术在实践中缺少形式化的零知识和/或正
11、确属性的支撑，导致这一切的是出于效率或其它原因的参数选择问题。事实上，许多这类概念是渐进的，并不能直接应用到实用协议中来。2 Fiat-Shamir鉴别协议。掌握秘密接受证明认为次都成功完成，。如果连续且独立次如下的步骤循环执行协议执行作为公开密钥。登记，并向计算，互素的秘密选择一个与每一个声称者保密。和素数，但将型的模选择并公布一个信任中心一次性建立过程。其掌握知识证明次向验证者轮协议通过执行一个：证明者鉴别协议sABttvTn svnssnAqpqpnTsBtA)( . (2) ) mod( 1 1 (1.2) RSA (1.1). (1) 3Shamir-Fiat2摘摘要要 协协议议1
12、12 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-Fiat22222的情况。是为了排除。注意验证，由于或者，得根据就可以接受证明。了拒绝证明，否则，验证，如果。如果者或如果，回答计算并发送给。给发送并，或者比特问题随机的选择一个。给证据发送，并且，承诺选择一个随机数续鉴别协议rynsvnvxy xyenvxyByensryeryyBAAeeeBBnrxnrrAe 协协议议1 1BA) (mod 2nr
13、x ) (mod 0 2证明。拒绝接受证明；否则则，并如果BBnvxyye1 0，e)(mod ns ry e2 Fiat-Shamir 鉴别协议(续)2 Fiat-Shamir鉴别协议(续)的身份。受回答正确的情况下才接都轮个问题只有在全部次，协议需要执行或例如，的小数值可能性到一个可以接受为了减少欺骗的可能可以不被发现。问题，因此有的一个他人只能至多回答其中回答两个问题，但是其的证明者可以个知道是用来阻止欺骗的。一者而言对诚实证明，另一个容易的问题她掌握的秘密知识其中一个需要有能力回答两个问题，要求或测试证明。提问做如下解释和非正式的可以对AttBtttssAet)( )40 = 20 =
14、 (21/2)()( 协议(1)1 评评述述. .2 Fiat-Shamir鉴别协议(续)不能预测实时问题。并，因为并不能冒充管可以模拟证明过程，就是零知识属性。尽产生的对不可区分，这的概率分布实际上与，信息对的方法，但对建立。虽然这并不是或定义，选择自己很好的模拟：随机好可以为验证者恰，产生的信息对。由并不知道随机数的信息，因为也没有提供任何关于，然而答案的秘密是独立于答案BABAyxAnv yyx yByxArBsns rysAry ) () mod(/ ) () mod( (2)续(22 评评述述. .3 Feige-Fiat-Shamir鉴别协议。，这里计算的分解。否则将导致可以得到保
15、证，但是这一点几乎肯定，要求原因，由于技术。，个随机整数选择做如下步骤每个实体每个实体秘密参数选择为定义的安全参数。和分解困难。整数，并且满足向所有用户公开公共模信任中心系统参数选择自己的身份。证明轮协议向验证者次执行一个通过摘要：证明者鉴别协议kinsvnnsnsssskAtknqpnTBtAiiiik 1 ) (mod (2.2)1 )( (1 1 . . . (2.1). . (2) . (1)3Shamir-Fiat-Feige 221协协议议2 23 Feige-Fiat-Shamir鉴别协议(续)0 (0 ) (mod (3.4)( ) (mod )( (3.3) . . . ()
16、( (3.2) )( )mod( 11 (3.1) . . . ( . (3) . . . () . . . ( ) ( (2.3)(Shamir-Fiat-Feige 121212212121的情况。者选择后一条是为了防止攻击。和，并验证计算的乘积。问中的和定义在提。：答案计算并发送给。，比特向量一个提问发送给。给证据发送，并并计算，选择一个随机整数。；，的真实公开密钥知道轮都能成功。假定的身份，如果全部将接受次。下面的步骤执行协议执行程。这是一次性的建立过，密密钥知道自己的秘的公开密钥，当然只有登记为；，将就这样认证自己的身份，照片例如，通过非密码手段向续鉴别协议rzxznvyzBsrns
17、ryBAeeekABBx n rxnrrAnvvvABtABtsssAAnvvvTTAkjejjkjejkkkkjj协协议议2 23 Feige-Fiat-Shamir鉴别协议(续)AB) (mod 2nrx 拒绝证明。否则，接受证明；则，并且如果BBxznvyzjjeej ) 0(mod 12 1 0 ) . . . (1，ikeee) (mod 1nsryjej3 Feige-Fiat-Shamir鉴别协议(续)。和因为的身份，这是并接受计算。数值计算并发送给。，比特向量一个发送给。，并发送它给，计算选择。，密钥是，秘密；，公开密钥是。，和，计算。，个随机整数选择做如下步骤实体被定义为安全
18、参数。和。整数，并公布，选择素数信任中心明选择小的参数以利于说0528015 ) (mod (3.4)403104 ) mod ( (3.3)1) 0 (0 3 (3.2)528015 1279 (3.1) (3)4646) 43215 (157553913) 429490 338402 (112068 (2.3)429490 338402 112068 (2.2)4646 43215 1573 ) (2.1. (2)1 3 553913 811 683 (1)(323321321zxzAnvyzBnsryBAABBxrAvvvsssAtkqpnqpT 例例子子1 13 Feige-Fiat-
19、Shamir鉴别协议(续)。和数知识证明，这里假定参况下是对知识的一个零议在有可信服务器的情零知识和正确属性。协的分解问题。算。这个问题等价于计的模平方根的困难问题合数赖于计算未知分解的大安全假设需求。安全依的概率保证冒充成功。击也只有是困难的，最好的攻分解安全的，也就是，如果息攻击可以证明是抵抗选择消伪造概率。)(log ) log O(log (3) (2)2协议 (1)ntnknnntk2 评评述述. .3 Feige-Fiat-Shamir鉴别协议(续)。意味着减少作为常数，增加信开销。乘积行，可以减少计算和通协议执全参数使得仅需要一轮安全平衡。通过平衡安。，的安全：；，的安全：对于参
20、数选择，是适合的选择。具体的和通信的平衡，算，存储，试已经足够。考虑到计用户防御冒充的鉴别测对于个人万分之一，这在现实中冒充成功的概率只有百就可以保证满足和数参数选择。选择安全参tktktktkktktk (5)5 6 2 4 5 2181 20 (4)续(3020评评述述. .3 Feige-Fiat-Shamir鉴别协议(续)，但并不增加轮数。伪造可以降低错误率行循环相对于串执行在交互证明中这种并行这样做仍然是安全的。条消息并行执行，轮的让全部协议的平行版本，可以少。那么通信复杂度可以减的验证也做相应修改，而不是值一个比特例如，发送给如果的模联系起来。需要将每个用户和他们仍然自己的模，做改
21、变，每个用户选择步的第修改考虑。)()(3 (6.3)(hash)128( (6.2) (1) (6.1) (6)续(tBxxhBAT协协议议2 2评评述述. .3 Feige-Fiat-Shamir鉴别协议(续)。并将其交给的平方根就可以计算的分解，知道。由于信任中心是一个适当的公开函数计算出来，这里，用和其他实体可以由，的公开值。的信息或其它验证者希望验证例如，名字，地址，的身份不同位串识每个实体分配一个标份基方案。方案可以改造成如下身AsvnTfiIfvBTkivAIATiiAiiA )( 1 )( (6.4)续(评述.评述.3 Feige-Fiat-Shamir鉴别协议(续)的离线攻击
22、。须适当增加以防止对的比特长度必方案，提问以变成一个非交互签名交互鉴别方案就可。通过这一变换，一个者的作用基本起到一个验证的一个连接与被签名消息据代替，这里是证值用单向随机提问者的数字签名方案：将验证顺序的鉴别协议转变为回答提问一个证据如下的一般方法可以将hash )()|( hash (6.5)续(ehmxmxhee评述.评述.4 GQ鉴别协议)( )( (1.3) (mod 1)1)( 1 )(3 (1.2)RSA( RSA (1.1). (1)(3GQ 1并保证其真实性。，统参数所有用户都可以获得系。，并计算他的秘密指数，这里，满足定义一个公开指数必定不可能。，分解作为。并产生模和型素数
23、选择一个秘密的随机绑定。身份负责将公开密钥与用户一个为各方信任的权威系统参数选择。通过掌握知识份证明自己的身轮协议向验证者通过一个摘要：证明者鉴别协议nvvsqpvvTnqpnqpTTsBAA协协议议3 34 GQ鉴别协议(续)接受其身份。次执行都成功的情况下仅在证明自己的身份；次执行如下步骤向通过协议执行。交给审定合格的数据将秘密。，困难隐含了假定分解一个公开的冗余函数。是，这里满足，冗余身份可以计算，从这个身份值被赋予唯一一个身份每个用户每个用户参数选择续鉴别协议tBBtAAnJsTnJnfnJIfJIAsAAAAAAA . (3) (mod)( )( (2.2)1 )( ( 1 )( )
24、( (2.1). (2)(GQ 协议3协议34 GQ鉴别协议(续) )0 (0 )(mod )( (3.5) )()(mod (3.4)1 )( (3.3) ( (3.2) (mod )(1 1 )( (3.1)(GQ 。攻击者选择后一种情况是为了阻止身份的证明。对其，就接受和，并且如果，计算建立从见上面之后，用收到。回答给计算并发送。，给，提问数选择并发送一个随机整。给，发送整数对。证据，并且计算，承诺选择一个随机整数续鉴别协议rAzxznyJzJIfyBBnsryAAveeBBxIAnrxnrrAveAAAeAAv协议3协议34 GQ鉴别协议(续)BA) (mod nrxIvA，拒绝证明。
25、否则，接受证明；则并且如果BBxznyJzveA , ) 0(mod vee1 ，这里) (mod nsryeA4 GQ鉴别协议(续)。和的身份，这是因为并接受计算。给发送。给发送随机提问。给，发送整数对。并计算选择。发给将审定合格的数据。的冗余身份参数是假定让全体用户得到。，系统参数。，并且计算，选择计算。，并且计算，选择素数权威使用小参数并且0 89525 )(mod (3.5)83551 ) (mod (3.4)38980 (3.3) 89525) ( (3.2)89525 ) (mod 65446 (3.1) (3)403154 ) (mod )( (2.2)34579 (2.1) (
26、2)420491) (54955 (1.3)233875 mod 54955 419184 1)1)( (1.2)420491 739 569 (1.1) (1)1) ( 1zxzAnyJz BBnsryAAeBBIAnrxrAAnJsTJAvsvqpTqpnqpTtveAeAAvsAAA例例子子2 24 GQ鉴别协议(续)是困难的。的因子情况下通常认为知道更困难，但在不这并不比分解是攻击协议的方法；问题解也就是，求次平方根的模合整数需要的安全假设。计算者存在的环境而定。比特长度应该根据攻击的攻击协议。推荐的计算并进一步像验证者一样的概率成功事先猜测证明者可以有效计算。一个冒充的有利于一些值如
27、；却需要许多轮交互协议，这里比较决定安全等级，中伪造的概率。在评述nnvnvyJxevvvvveA )RSA( (2)( / 112 )2 Shamir-Fiat( 协议 (1)163.4 GQ鉴别协议(续)误审定合格的数据。假身份的错止攻击者计算出对应虚使用冗余函数的目是阻的多项式。必须不大于为常数的情况，对于的渐进上限：是一个整数，考虑，这里要求方案的零知识属性对于相反，零知识属性。与正确性。必须渐进增加快于要求是，技术上对于正确属性的是一个常数，。如果，伪造的概率是，对于一般参数比特素数。是一个而方案建议正确属性。在实践中，评述 (5) log ) O(log GQ (4)loglog)
28、(1 GQ (3)续(ntvt cnvt ntvvtvnkvtct.5 Schnorr身份鉴别关联得到。与秘密知识钥密通过认证证书将其公开，鉴别不给出知识来证明其掌握秘密根据一个提问个时变的方式以一。基本思想是证明者也使得交互的数据减少。当然，使用这种群的乘法群，这里阶为的改进源于使用整数模进一步重要的计算效率。者计算能力有限的情况开销，这非常适合证明算算以减少证明者实时计难性。设计允许预先计离散对数问题的困鉴别协议的安全性依赖avAaaeApqqp)()(1)( |Schnorr5 Schnorr身份鉴别(续)hash()( )( (1.3)1 1 (1.2)(1 (1.1). (1)3Sc
29、hnorr 。数和任意一个签名机制函适当的公开涉及在签名之前的一个。签名的对消息，它可以验证的验证公开密钥的函数中心和信任，系统参数每一方得到一份真实的。，的元选择一个乘法阶为可能。的离散对数在计算上不保证模整除。可以被另一个素数满足选择一个适当的素数系统参数选择身份。证明自己的轮协议向验证者通过一个摘要：证明者鉴别协议TTSmSmTTqppqpqppBA协议4协议45 Schnorr身份鉴别(续)绑定。和将，书颁发的证，最后得到一个由传递给份，接着将真实的验证自己的身例如，出示护照通过传统方式向。，并计算，选择一个秘密密钥。选择一个唯一身份每个实体每个用户参数选择。全等级定义一个安，例如，选
30、择一个安全参数续鉴别协议vIvISvIcertTTvTApvqaaAIAqttAATAAaAtt)( ( )( (2.3) (mod 1 0 (2.2) (2.1). (2)2( 2 40) ( (1.4)(Schnorr 协议4协议45 Schnorr身份鉴别(续)的身份。，接受，如果计算。给回答并发送检查。，给，提问随机数从未使用过的实性，接着发送一个的真的公开密钥中的签名验证在证书通过。给，并发送证据计算，承诺选择一个随机数验证自己的身份。按如下步骤向协议执行续鉴别协议AxzpvzBBqreayeAAeevAcertTBBxcertpxqrrABAeyttAAr ) (mod (3.4)
31、 (mod )(21 (3.3)21 )()( (3.2) )() (mod )( 1 1 )( (3.1) . (3)(Schnorr 协协议议4 45 Schnorr身份鉴别(续)BA) (mod pxcertrA，绝证明。拒接受证明；否则，则，如果BBpxvzey) (mod qeet21，这里) (mod qreay5 Schnorr身份鉴别(续)。的身份，由于并接受计算。给发送数字。给发送随机提问。给并发送选择。并计算选择一个秘密密钥。选择参数。，系统参数是得到。可以通过计算；的生成元是一个模整除。可以被素数，这里选择素数使用小参数便于说明例子xzApvzBB q r e ayAAe
32、BBpxrApvaAt pqppeyraqp37123) (mod (3.4)255)(mod (3.3)129 (3.2)37123 ) (mod 274 (3.1) (3)7355 ) (mod 357 (2)8 (1.4)11444) 443 (48731 (1.3)11444 )(mod6 48731 (1.2)443 148731 (1.1) (1)( 1)/(35 Schnorr身份鉴别(续)给搅乱。被随机数是一个随机数，信息，因为的有用暴露任何关于。简要说来，协议没有计算知识都应该确实有能力完成协议的也就是，任何可以成功的证明，到协议是一个对知识正确属性。我们可以看离散对数攻击。
33、阻止其它可能的离线存储平衡，目前推时间会破坏在一秒钟完成，略大的推荐的参数，回答可以是最初，可以忽略；的概率出提问测必须足够大使得正确猜中，伪造概率。在ryxaaAaqqqtet tt (2)2荐2 2 40 2 协议 (1)1608024评评述述. .5 Schnorr身份鉴别(续)计算。预先离线法，这里假定模幂可以需要在线计算一个模乘于证明者仅鉴别的一个优势在于对离线计算。对应的比特相比较。比特与也仅将这之后而不是全部来缩减，比特例如，最后比特的预先定义的传输输的数据开销可以通过传输带宽。协议所要传。选择根据是例如，如果自己所不能计算的，这是，的解得到了方程因为通过交互，性，协议不具有零知识属零知识属性。对于大的Schnorr (5)( (4) ()() (mod (3)续(ztBttxxeBeyxpvxBeey评评述述. .谢谢！
