《零知识证明》PPT课件.ppt

零知识证明,概念,“零知识证明”zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。,1）A要向B证明自己拥有某个房间的钥匙，假设该房间只能用钥匙打开锁，而其他任何方法都打不开。这时有2个方法：（一）A把钥匙出示给B，B用这把钥匙打开该房间的锁，从而证明A拥有该房间的正确的钥匙。（二）B确定该房间内有某一物体，A用自己拥有的钥匙打开该房间的门，然后把物体拿出来出示给B，从而证明自己确实拥有该房间的钥匙。后面这个方法属于零知识证明。好处在于在整个证明的过程中，B始终不能看到钥匙的样子，从而避免了钥匙的泄露。,零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。零知识证明必须包括两个方面，一方为证明者P，另一方为验证者V。证明者试图向验证者证明某个论断是正确的，或者证明者拥有某个知识，却不向验证者透露任何有用的消息。零知识证明目前在密码学中得到了广泛的应用，尤其是在认证协议、数字签名方面。,在Goldwasser等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明”。80年代末，Blum等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。大量事实证明，零知识证明在密码学中非常有用。,Quisquater-Guillon零知识协议,1990年，Quisquater和Guillon提出一种形象的基本零知识协议的例子。如下图所示，该图表示一个简单的迷宫，只有知道秘密口令的人才能打开C 和之间的密门。现在，P希望向V证明P能够打开此门，但是又不愿意向V泄漏P掌握的秘密口令。为此，P采用了所谓的“分隔与选择”技术实现一个零知识协议。,分隔与选择（cut and choose）协议,A将蛋糕分成两半；B为自己选择其中的一半；A得到剩下的一半。这是一种公平协议，A如果分割不均匀，B总能选择对自己有利的一半。这个协议为交互零知识证明的雏形。,1)V 站在点。(2)P 一直走到迷宫深处，随即选择点或者点。(3)在 P消失后，V走到点。(4)V 向 P 喊叫，要她：从左通道出来，或者从右通道出来。(5)P答应了，如果有必要她就用秘密口令打开密门。P 和 V重复第(1)至第(5)步 n 次。,在上述协议中，如果P不知道秘密口令，他只能从来路返回到B点，而不能走另外一条路。此外，P每一次猜对V要求他走哪一条路的概率是1/2。因此，每一轮协议P能够欺骗V的概率是1/2。执行n轮协议后，P成功欺骗V的概率是1/2n。嘉定n=16，则执行16轮协议后，P 成功欺骗V的概率是1/216=1/65536。于是，如果P能够16次按V的要求路线返回，V即能证明P确实知道秘密口令。同时，V无法从上述证明过程中获取丝毫有关P的秘密口令的消息。所以，这是一个零知识协议。,Hamilton回路零知识协议,许多计算上困难的问题可以用来构造零知识协议。在图论中，图 G中的回路是指始点和终点相重合的路径，若回路通过图的每个顶点一次且仅一次，则称图 G为哈密尔顿回路，构造图 G的哈密尔顿回路是 NPC 问题。,假定 P知道图 G的哈密尔顿回路，并希望向 V证明这一事实，可采用如下协议：(1)P 随机地构造一个与图 G同构的图 W。并将 W 交给 V。(2)V 随机地要求 P做下述两件工作之一：证明图 G和图 W 同构；指出图 W 的一条哈密尔顿回路。,(3)P 根据要求做下述两件工作之一：证明图G和图 W 同构，但不指出图 G或图 W 的哈密尔顿回路；指出图 W 的哈密尔顿回路，但不证明图 G和图 W 同构。(4)P 和 V重复以上过程 n 次。,协议执行完后，V 无法获得任何信息使自己可以构造图 G 的哈密尔顿回路，因此该协议是零知识证明协议。事实上，如果 P 向 V 证明图 G 和图 W 同构，这个结论对 V 并没有意义，因为构造图 G的哈密尔顿回路和构造图 W 的哈密尔顿回路同样困难。如果 P向 V指出图 W 的一条哈密尔顿回路，这一事实也无法向 V提供任何帮助，因为求两个图之间的同构并不比求一个图的哈密尔顿回路容易。在协议的每一轮中，P都随机地构造一个与图 G同构的新图，因此不论协议执行多少轮，V 都得不到任何有关构造图 G 的哈密尔顿回路的信息。,Goldwasser等人提出的零知识证明是交互式的，也就是证明者和验证者之间必须进行双向对话，才能实现零知识性，因而称为交互零知识证明。,在交互零知识证明的研究中，目前受到关注的有两种基本模型。一种是GMR模型，在这种模型中，证明者具有无限的计算能力，验证者具有多项式时间的计算能力。需要证明的是语言成员问题，即输入I是否是语言L中的一个成员。GMR模型不是真正的零知识证明，这是因为在证明中，证明者向验证者揭露了有关知识的1比特信息，即I L是否成立。但除此之外，再没有其他任何附加的信息泄露给验证者，通常称这种交互零知识证明为成员零知识证明或定理零知识证明。,另一种是FFS模型，在这种模型中，证明者和验证者均具有多项式时间的计算能力，证明者的目的不是向验证者证明IL，而是证明他知道I是否属于L。FFS模型是真正的零知识证明，因为在证明中，验证者没有得到任何信息，他连IL还是I L都不知道，但他相信这个证明，通常称这种交互零知识证明为知识零知识证明或身份零知识证明。,从实用角度考虑，要保证用户身份识别的安全性，识别协议至少要满足以下条件：识别者A能够向验证者B证明他的确是A。在识别者A向验证者B证明他的身份后，验证者B没有获得任何有用的信息，B不能模仿A向第三方证明他是A。,Feige-Fiat-Shamir 身份识别协议,在一个安全身份识别协议中，我们希望识别者 Alice 能向验证者 Bob 电子地证明他的身份，而又没有向 Bob 泄露他的识别信息，这十分类似于零知识的思想。1986年，Feige，Fiat 和 Shamir基于零知识的思想设计了一个零知识身份识别协议，这就是著名的 Feige-Fiat-Shamir 零知识身份识别协议。该协议的目的是证明者P向验证者V证明他的身份，且事后V不能冒充P。,简化的 Feige-Fiat-Shamir 身份鉴别方案,在发放私人密钥之前，仲裁方随机选取一个模数n，n为两个大素数之积。实际中，n应至少为 512 位长，尽量接近 1024 位。n值可在一组证明者之间共享。,Feige-Fiat-Shamir 身份鉴别方案,其他身份识别协议,Schnorr 鉴别协议,攻击身份的零知识证明例子,象棋大师问题一个有预谋的用户A想使其他人相信她是一个象棋高手，她可以通过这样的方法来实现：她找到两位世界顶尖级象棋界高手B和C，向他们提出挑战，并定于同一时间，在同一地点的不同房间和他们进行比赛。在比赛的过程中，每当B或C下一步棋，A就跑到隔壁的房间如法炮制，走同一步棋。也就是说，尽管B和C以为他们都在和A对弈，但实际的情况是B和C在彼此对弈。无论最后是B和C哪个赢，A总会是某一局棋的得胜者，从而向其他人证明她的确是一名象棋高手。该过程是对身份的零知识证明的一种攻击。,黑手党骗局A正在B(黑手党)的餐厅吃饭。此时C（黑手党）按照计划来到一家D开的高档珠宝店买东西。B和C随时可以通过一条秘密的无线电线路保持联系，而A和D都对即将到来的骗局一无所知。当A准备结账并对B证明其身份时，B立刻发信号给C让他准备行动，此时的C早已挑好了许多名贵珠宝，于是他向D证明他的身份。当D开始提问时，C用无线电把问题传给B，B则向A询问同样的问题，得到了答复后B再把答案通过无线电传给C。,