零知识证明技术

第十六讲零知识证明技术Peggy：“我知道联邦储备系统计算机的口令，McDonald的秘密调味汁的成分，以及Knuth第5卷的内容。”Victor：“不，你不知道。”Peggy：“我知道。”Victor：“你不知道！”Peggy：“我确实知道！”Victor：“请你证明这一点！”Peggy：“好吧，我告诉你！”她悄悄地说出了口令。Victor：“太有趣了！现在我也知道了。我要告诉《华盛顿邮报》。”许多年前，有报道称小偷在一个超市中放置假的ATM机。当人们将银行卡插入机器并输入鉴别身份的秘密时，机器将这些信息记录下来并反馈消息说机器不能接受这种类型的银行卡。小偷接下来就可以制造假的银行卡，并使用得到的身份鉴别秘密信息到真的ATM机上提取现金。如何避免这一情况发生？在很多情况下需要出示鉴别身份的秘密或口令来完成交易。任何人在得到这个秘密再附加一些(几乎公开的)身份信息之后，就可以冒充这个人。我们需要解决的问题就是使用秘密但在使用的过程中不留给攻击者任何可以重复使用的信息。这就产生了零知识证明技术。本讲提要零知识证明概念总揽Fiat-Shamir鉴别协议Feige-Fiat-Shamir鉴别协议GQ鉴别协议Schnorr鉴别协议1零知识证明概念总揽1.1思想1.1思想(续)Peggy知道这个洞穴的秘密。她想对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思想(续)评述.协议使用的技术叫做分割选择技术(cutandchoose)，因为它类似如下将任何东西等分的经典协议：(1)Peggy将东西切成两半。(2)Victor给自己选择一半。(3)Peggy拿走剩下的一半。Peggy最关心的是第(1)步中的等分，因为Victor可以在第(2)步选择他想要的那一半。1.2交互证明系统和零知识证明协议零知识证明协议是交互证明系统的一个实例，这里一个证明者和一个验证者交互多轮。证明者的目标是让认证者相信声称的正确性，例如，声称掌握一个秘密。验证者要么接受证明要么拒绝证明。这与传统的数学概念的证明有所不同，交互游戏的证明是随机而不是绝对的。由于这个原因，一个交互证明常常被称为协议证明。1.2交互证明系统和零知识证明协议(续)用于鉴别的交互证明可以被形式化为知识证明。证明者A掌握某个秘密s，并通过正确的回答验证者B所提出的问题(涉及的是公开已知的输入和协商一致的函数)使其相信确实掌握秘密s，当然，回答这些问题需要秘密s。注意证明掌握秘密s不同于证明s存在。一个交互证明是知识证明如果证明满足完备性和正确性属性。1.2交互证明系统和零知识证明协议(续)定义1(完备属性)一个交互证明(协议)是完备的，如果给定一个诚实的证明者和认证者，协议就能以压倒的概率获得成功(也就是，验证者接受证明者的宣称)。评论.完备性可以看作是协议在诚实的参与者执行的情况下的一般要求。对压倒的概率的定义依赖具体应用，但通常隐含失败的概率无实际意义。1.2交互证明系统和零知识证明协议(续)定义2(正确属性)一个交互证明(协议)是正确的，如果存在一个平均多项式时间算法M满足如下性质：如果一个不诚实的证明者(A)可以以不可忽略的概率成功的与B执行协议，M则可以用来得到这个证明者的知识(本质上等于A的秘密)，这将使得后续的协议执行以压倒概率获得成功。1.2交互证明系统和零知识证明协议(续)由于任何有能力冒充A的一方都等同于知道A的秘密知识(M可以在多项式时间内来计算它)，正确属性保证了协议确实提供了对知识的证明–知识等价于询问的正确应答。正确属性因此阻止了不诚实的证明者使诚实的验证者相信知识的可能。1.2交互证明系统和零知识证明协议(续)定义3(零知识属性)一个知识证明的协议有零知识属性，如果协议可模拟如下功能：存在一个平均多项式算法(模拟器)，它可以不和真实的证明者交互就可以产生一些证明必要的交互消息。这些消息副本与同真实的证明者交互产生的结果不可区分。1.2交互证明系统和零知识证明协议(续)评述.(1)零知识属性表明一个证明者执行协议(即使与恶意验证者交互)不会透露任何信息(即除了特定的声称正确以外的关于他的秘密知识)，这无异于在多项式时间从公开信息中计算。因此，参与者不会增加后续冒充成功的机会。1.2交互证明系统和零知识证明协议(续)(2)考虑一个观查者C观测证明者A与验证者B(BC)一个零知识证明协议交互过程，且B确定了A掌握某个知识。向B证明的过程并不能给C任何担保。(事实上，A和B可能事先串通应答内容来欺骗C。)相似情况，记录零知识证明协议的交互也不能进行回放。这就是零知识属性的基本思想，即证明过程可以由验证者单独模拟完成。1.2交互证明系统和零知识证明协议(续)(3)零知识属性(定义3)不能保证协议是安全的(也就是，获得秘密知识的可能性可以忽略)。同样，正确属性(定义2)也不能保证协议安全。这两个属性只有在攻击者面临计算困难问题的时候才有意义。1.3零知识证明协议的一般结构案。就限定了将来的可能答问题的集合，因此，也回答在本次协议执行中所能随机性，并限定了一个每一次协议执行的的公开证据。这提供了承诺，并从中计算相关合上的元素做一个秘密择一个在事先定义的集结构：证明者随机的选交互零知识协议的一般以上描述了一大类三次：：：ABABABA回答提问证据1.3零知识证明协议的一般结构(续)的概率。功制循环次数降低欺骗成果需要，就可以通过控一个循环执行过程，如检查是否正确。协议是做出回答，而，给接着选择一个问题提交的秘密知识。帮助分析回答一个问题，并不能开证据提出的问题，而有能力回答所有根据公才道秘密知识的合法根据协议设计，只有知BAABAA1.4零知识协议VS.非对称协议(1)使用不退化：协议具有零知识属性因此不会因为重复使用而降低安全性并可阻止选择消息攻击。这可能是零知识技术在实践中最吸引人之处。(2)无需加密：许多零知识技术都不需要使用加密算法。(3)效率：虽然一些零知识基技术非常有效，但是具有零知识属性的协议通常比没有零知识属性的非对称协议需要更多通信和计算开销。更为有效的实用零知识基方案通常源于交互证明的特性，而不是它的零知识特性。1.4零知识协议VS.非对称协议(续)(4)没有证明的假设：许多零知识协议(“证明知识”)本身依赖于和非对称技术一样的未经证明的假设(例如，分解的困难)。(5)零知识基与零知识：虽然有着严谨的理论支持，许多基于零知识概念的技术在实践中缺少形式化的零知识和/或正确属性的支撑，导致这一切的是出于效率或其它原因的参数选择问题。事实上，许多这类概念是渐进的，并不能直接应用到实用协议中来。2Fiat-Shamir鉴别协议。掌握秘密接受证明认为次都成功完成，。如果连续且独立次如下的步骤循环执行协议执行作为公开密钥。登记，并向计算，，互素的秘密选择一个与每一个声称者保密。和素数，但将型的模选择并公布一个信任中心一次性建立过程。其掌握知识证明次向验证者轮协议通过执行一个：证明者鉴别协议sABttvTnsvnssnAqpqpnTsBtA)(.(2))mod(11(1.2)RSA(1.1).(1)3Shamir-Fiat2摘要协议12Fiat-Shamir鉴别协议(续))00)(mod)(mod()(mod0(2.4)1)()(mod0)()((2.3)10)((2.2))(mod)(11)((2.1))(Shamir-Fiat22222的情况。是为了排除。注意验证，由于或者，得根据就可以接受证明。了拒绝证明，否则，验证，如果。如果者或如果，回答计算并发送给。给发送并，或者比特问题随机的选择一个。给证据发送，并且，承诺选择一个随机数续鉴别协议rynsvnvxyxyenvxyByensryeryyBAAeeeBBnrxnrrAe协议1BA)(mod2nrx)(mod02证明。拒绝接受证明；否则则，并如果BBnvxyye1}{0，e)(modnsrye2Fiat-Shamir鉴别协议(续)2Fiat-Shamir鉴别协议(续)的身份。受回答正确的情况下才接都轮个问题只有在全部次，，协议需要执行或例如，的小数值可能性到一个可以接受为了减少欺骗的可能可以不被发现。问题，因此有的一个他人只能至多回答其中回答两个问题，但是其的证明者可以个知道是用来阻止欺骗的。一者而言对诚实证明，另一个容易的问题她掌握的秘密知识其中一个需要有能力回答两个问题，要求或测试证明。提问做如下解释和非正式的可以对AttBtttssAet)()40=20=(21/2)()(协议(1)1评述.2Fiat-Shamir鉴别协议(续)不能预测实时问题。并，因为并不能冒充管可以模拟证明过程，就是零知识属性。尽产生的对不可区分，这的概率分布实际上与，信息对的方法，但对建立。虽然这并不是或定义，选择自己很好的模拟：随机好可以为验证者恰，产生的信息对。由并不知道随机数的信息，因为也没有提供任何关于，然而答案的秘密是独立于答案BABAyxAnvyyxyByxArBsnsrysAry)()mod(/)()mod((2))续(22评述.3Feige-Fiat-Shamir鉴别协议。，这里计算的分解。否则将导致可以得到保证，但是这一点几乎肯定，要求原因，由于技术，，，，，个随机整数选择做如下步骤每个实体每个实体秘密选择为定义的安全参数。和分解困难。整数，并且满足向所有用户公开公共模信任中心系统参数选择自己的身份。证明轮协议向验证者次执行一个通过摘要：证明者鉴别协议kinsvnnsnsssskAtknqpnTBtAiiiik1)(mod(2.2))1)((11...(2.1)..(2).(1)3Shamir-Fiat-Feige221协议23Feige-Fiat-Shamir鉴别协议(续))0(0)(mod(3.4))()(mod)((3.3))...()((3.2))()mod(11(3.1))...(.(3))...()...()((2.3))(Shamir-Fiat-Feige12112111的情况。者选择后一条是为了防止攻击。和，并验证计算。的乘积问中的和定义在提：答案计算并发送给。，，比特向量一个提问发送给。给证据发送，并并计算，，选择一个随机整数。；，，的真实公开密钥知道轮都能成功。假定的身份，如果全部将接受次；下面的步骤执行协议执行程。。这是一次性的建立过，，密密钥知道自己的秘的公开密钥，当然只有登记为；，，将就这样认证自己的身份，照片例如，通过非密码手段向续鉴别协议rzxznvyzBsrnsryBAeekABBxnrxnrrAnvvABtABtssAAnvvTTAkjejjkjejkkkkjj协议23Feige-Fiat-Shamir鉴别协议(续)AB)(mod2nrx拒绝证明。否则，接受证明；则，并且如果BBxznvyzjjeej)0(mod121}{0)...(1，，，，ikeee)(mod1nsryjej3Feige-Fiat-Shamir鉴别协议(续)。和因为的身份，这是并接受计算。数值计算并发送给。，，比特向量一个发送给。，并发送它给，计算选择。，，密钥是，秘密；，，公开密钥是。，和，计算。，，个随机整数选择做如下步骤实体被定义为安全参数。和。整数，并公布，选择素数信任中心明选择小的参数以利于说0528015)(mod(3.4)403104)mod((3.3)1)0(03(3.2)5280151279(3.1)(3)4646)43215