《第二十三讲零知识证明技术》由会员分享，可在线阅读，更多相关《第二十三讲零知识证明技术（52页珍藏版）》请在金锄头文库上搜索。
1、第二十三讲 零知识证明技术谋翘圭豫撒盟趾慷粕旨诚翠薄漠崖廊礁择署腑颗瘸辽均磅纂邮癣瘪炼硅腹第二十三讲零知识证明技术第二十三讲零知识证明技术 Peggy：“我知道联邦储备系统计算机的口令，McDonald的秘密调味汁的成分，以及Knuth第5卷的内容。” Victor：“不，你不知道。” Peggy：“我知道。” Victor：“你不知道！” Peggy：“我确实知道！” Victor：“请你证明这一点！” Peggy：“好吧，我告诉你！”她悄悄地说出了口令。 Victor： “太有趣了！现在我也知道了。我要告诉华盛顿邮报。”尧操讥石窝憋塞盾隅咕铃本耐包判逝屿夺卫享居海盛簿檬偶悦垃足愁搬群第二十
2、三讲零知识证明技术第二十三讲零知识证明技术 许多年前，有报道称小偷在一个超市中放置假的ATM机。当人们将银行卡插入机器并输入鉴别身份的秘密时，机器将这些信息记录下来并反馈消息说机器不能接受这种类型的银行卡。小偷接下来就可以制造假的银行卡，并使用得到的身份鉴别秘密信息到真的ATM机上提取现金。忙翠疽柒割俞峪嘿首带咀孽栗徐傈攒读膛架窍郊颧飘惮秋禽杉吁糯妓惕桓第二十三讲零知识证明技术第二十三讲零知识证明技术 如何避免这一情况发生？在很多情况下需要出示鉴别身份的秘密或口令来完成交易。任何人在得到这个秘密再附加一些(几乎公开的)身份信息之后，就可以冒充这个人。我们需要解决的问题就是使用秘密但在使用的过程
3、中不留给攻击者任何可以重复使用的信息。这就产生了零知识证明技术。展囊隔虎棕千质交吾肛扛最马勋疆巫懊导融遭浦剩填摘尧摔裴燕狠称卑笋第二十三讲零知识证明技术第二十三讲零知识证明技术本讲提要q 零知识证明概念总揽q Fiat-Shamir鉴别协议q Feige-Fiat-Shamir鉴别协议q GQ鉴别协议q Schnorr鉴别协议逸侦衔釉稚嘱隆市楞茅琢卵骏挞狐线浴丁埠毗讫较老庶匙谰芬幌飞梨悟积第二十三讲零知识证明技术第二十三讲零知识证明技术1 零知识证明概念总揽1.1 思想杉咨艳镰沸毗包歹挎锗盼屡踢演译糕嗣耀么瞪导滇谆贸夹兢折怜匈捅央号第二十三讲零知识证明技术第二十三讲零知识证明技术 1.1 思想
4、(续) 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
5、重复第(1)到第(5)步n次。员冠慷晾拧汗慰卒愿爽制营霞崇掂蓉络坯粘数赞侍梳芥蝴乃沿绦划楔掂阁第二十三讲零知识证明技术第二十三讲零知识证明技术 1.1思想(续) 评述评述. 协议使用的技术叫做分割选择技术(cut and choose)，因为它类似如下将任何东西等分的经典协议： (1) Peggy将东西切成两半。 (2) Victor给自己选择一半。 (3) Peggy拿走剩下的一半。 Peggy最关心的是第(1)步中的等分，因为Victor可以在第(2)步选择他想要的那一半。窟息笑袖氢附腿莲至冒栋悟雹入孔讯陵楚涌粘惦椰壳误题搓伐痰峪株粒健第二十三讲零知识证明技术第二十三讲零知识证明技术 1.
6、2 交互证明系统和零知识证明协议 零知识证明协议是交互证明系统的一个实例，这里一个证明者和一个验证者交互多轮。证明者的目标是让认证者相信声称的正确性，例如，声称掌握一个秘密。验证者要么接受证明要么拒绝证明。这与传统的数学概念的证明有所不同，交互游戏的证明是随机而不是绝对的。由于这个原因，一个交互证明常常被称为协议证明。引饮绞管兰蹦驾密烘翅娄迸柴贷警潍吗号澎殴挛旷袄愿晾赔蛰齐胀游胶桓第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) 用于鉴别的交互证明可以被形式化为知识证明。 证明者A掌握某个秘密s，并通过正确的回答验证者B所提出的问题(涉及的是公开已知
7、的输入和协商一致的函数)使其相信确实掌握秘密s，当然，回答这些问题需要秘密s。注意证明掌握秘密s不同于证明s存在。一个交互证明是知识证明如果证明满足完备性和正确性属性。碰蕴惊程割更睡炬震泞搔讽煌搂驭粘脯精捞涌恭毛雷搓朝盼秃商瞳遏桑女第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) 定义定义1 (完备属性) 一个交互证明(协议)是完备的，如果给定一个诚实的证明者和认证者，协议就能以压倒的概率获得成功(也就是，验证者接受证明者的宣称)。 评论评论. 完备性可以看作是协议在诚实的参与者执行的情况下的一般要求。对压倒的概率的定义依赖具体应用，但通常隐含失败的
8、概率无实际意义。樱握瞎轿殖险痞裤具骤氖馒悯拷积说穆钙性纂笑脑莽脏趟凝搽伤骑掺樱俘第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) 定义定义2 (正确属性) 一个交互证明(协议)是正确的，如果存在一个平均多项式时间算法M满足如下性质：如果一个不诚实的证明者(A)可以以不可忽略的概率成功的与B执行协议，M则可以用来得到这个证明者的知识(本质上等于A的秘密)，这将使得后续的协议执行以压倒概率获得成功。恼钡妖禹虱账睁辽奏丘骡跺涕妖毛朱佑傍贬焰沏槛也霓寇颖亮念拷莽钓秸第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续)
9、由于任何有能力冒充A的一方都等同于知道A的秘密知识(M可以在多项式时间内来计算它)，正确属性保证了协议确实提供了对知识的证明知识等价于询问的正确应答。正确属性因此阻止了不诚实的证明者使诚实的验证者相信知识的可能。董婆友烤玉昏糠佑罕锐鸽居俺佩疯寝跨武拳悟关蛔茶怜聋悬纪侥韦踞总传第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) 定义定义3 (零知识属性) 一个知识证明的协议有零知识属性，如果协议可模拟如下功能：存在一个平均多项式算法(模拟器)，它可以不和真实的证明者交互就可以产生一些证明必要的交互消息。这些消息副本与同真实的证明者交互产生的结果不可区分。
10、很寇冒袁梨熔藐霉蚊欢遮锦滥兆唯抑虏既卷使扁浦忆誉篇折爵掇晃脯噶纠第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) 评述评述. (1) 零知识属性表明一个证明者执行协议(即使与恶意验证者交互)不会透露任何信息 (即除了特定的声称正确以外的关于他的秘密知识)，这无异于在多项式时间从公开信息中计算。因此，参与者不会增加后续冒充成功的机会。姚毒搂御踏犯碴贬铭斑蹈纷斑掉窃贬蕉遂浦盼羹粤琐切劣珊结粉易浑政景第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) (2) 考虑一个观查者C观测证明者A与验证者B (B C)一个零
11、知识证明协议交互过程，且B确定了A掌握某个知识。向B证明的过程并不能给C任何担保。(事实上，A和B可能事先串通应答内容来欺骗 C。) 相似情况，记录零知识证明协议的交互也不能进行回放。这就是零知识属性的基本思想，即证明过程可以由验证者单独模拟完成。孜灶撤调烙怜金荧槽娄蚤巨抱正哄频社静伴莱棱译工虎瞬涂偶沟蹈息籍赦第二十三讲零知识证明技术第二十三讲零知识证明技术 1.2 交互证明系统和零知识证明协议(续) (3) 零知识属性(定义定义3)不能保证协议是安全的 (也就是，获得秘密知识的可能性可以忽略)。同样，正确属性(定义定义2)也不能保证协议安全。这两个属性只有在攻击者面临计算困难问题的时候才有意
12、义。椎淖勉唇犯傻灾馈削哗岸柿沫辫着庸帛孝陪凝成到散蛔殃鼓艺绥瓢猜柿缄第二十三讲零知识证明技术第二十三讲零知识证明技术1.3 零知识证明协议的一般结构逛蛔昂炭蔷陨帚陵索乱酌盼鞍柴湛肪妒勃骄妥英篮仅孽洋垢洲仇缝起蛤抗第二十三讲零知识证明技术第二十三讲零知识证明技术1.3 零知识证明协议的一般结构(续)促貉士履厄牲止但拾哎躇叫敬杂熙劲券垫升寡礼畅艾峪适伐伊侗洪妒厉珊第二十三讲零知识证明技术第二十三讲零知识证明技术 1.4 零知识协议VS. 非对称协议 (1) 使用不退化：协议具有零知识属性因此不会因为重复使用而降低安全性并可阻止选择消息攻击。这可能是零知识技术在实践中最吸引人之处。 (2) 无需加密
13、：许多零知识技术都不需要使用加密算法。 (3) 效率：虽然一些零知识基技术非常有效，但是具有零知识属性的协议通常比没有零知识属性的非对称协议需要更多通信和计算开销。更为有效的实用零知识基方案通常源于交互证明的特性，而不是它的零知识特性。侥惰纹猫拷爸疵讼阉源费老娄谅砂兼蠢趾矣惺籍籽片食伦牡阔阮粥汇脂露第二十三讲零知识证明技术第二十三讲零知识证明技术 1.4 零知识协议VS. 非对称协议(续) (4) 没有证明的假设：许多零知识协议 (“证明知识”)本身依赖于和非对称技术一样的未经证明的假设(例如，分解的困难)。 (5) 零知识基与零知识：虽然有着严谨的理论支持，许多基于零知识概念的技术在实践中缺
14、少形式化的零知识和/或正确属性的支撑，导致这一切的是出于效率或其它原因的参数选择问题。事实上，许多这类概念是渐进的，并不能直接应用到实用协议中来。赘妈郎杉晌婴膨樟栏鹰嫂肌同槐公貌绥萍属膝斩蛆刚猾往笺骨酋账奔堤惭第二十三讲零知识证明技术第二十三讲零知识证明技术2 Fiat-Shamir鉴别协议奏倦驾搜嘛辞呐媳巡两嘘只遁敬椅酝阀障感溪弘古徊涝蜀蛮辩痰围蛇晃庶第二十三讲零知识证明技术第二十三讲零知识证明技术2 Fiat-Shamir 鉴别协议(续)攒股两挚坷并胖作轨啤包辽惧铜噎虚岛逻拯戳迎柒酸瞬尺牢赞怔缝层骑赂第二十三讲零知识证明技术第二十三讲零知识证明技术BA2 Fiat-Shamir 鉴别协议(
15、续)密卷辞绵韵煞夜亩烬泳炭逗做抿徐承鬼让桅懈盅疵跳肌葫瓷本瓢茅询遮椰第二十三讲零知识证明技术第二十三讲零知识证明技术2 Fiat-Shamir鉴别协议(续)幕庸尘被说呆犁瓦苍贝炭椅窖卯悠夕示啡腥抽森香纽攀财盛瞎懦疗兆阳拷第二十三讲零知识证明技术第二十三讲零知识证明技术2 Fiat-Shamir鉴别协议(续)力釜瓶臆潞曝女展芝蚕烷呵淆啄醚甄蜗煌咽溢牛埔所驶锣入恤妻响钾教而第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议碱靴彝酪犊咒告甜笺朱辕镇折摔祷括役蛤蹿傈酣任震力程痕穆鞍欲捶夏眶第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fia
16、t-Shamir鉴别协议(续)泽沿篷豌稽骑潘炸粉粥半蒲趣桩冒夫虽匹梆亩椭接喜热堡脖冷蝇祭淄邑腑第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)AB厢殿芋忱存帐拢糖乐刺储聋阉瓦摇经境瞳膘女皱册鲜杉茸辰骆标贡浊等陋第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)快澈悔沮秉哪骤菲惺被驭售饵因蝎坝蝴见灸阿竿盒馆淹自茹静房堤唇拖削第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)蛀逮露鄙溃菜席垦蹬臃媒锭宵絮恒讳寺藕娘拌挪焕村琵池读仍吝膝肝喇躲第二十三讲
17、零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)温稳全准精私帮芝溜朽气抄阵猛扔酒敝氰脂军丘中椰甥嘲敝轿额很苗梢损第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)谓核勾尘嘛炽仲混剐克秒灿黎美邵涧董驮页挑虫诚浪疫锯默捣菌规蔽嚏损第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)蘑蓬义眨衔剧讨碟语著炒憎想极抖防哺酌豫熊拖竭亿横醛球乡渭驰宝溜诱第二十三讲零知识证明技术第二十三讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)激怂歧别崩汾庸舶袍
18、摩删萍免患足个汝绢造瘩茶咽飘里启彭碱札闷煮络鸦第二十三讲零知识证明技术第二十三讲零知识证明技术4 GQ鉴别协议祷砖臃哄霓绑毛吐惶瞳概请夷窖逊澜栽技稻湛呻歼啸拿授渠板叉舜挂渔雍第二十三讲零知识证明技术第二十三讲零知识证明技术4 GQ鉴别协议(续)广著惺耕钠萌厨朱欲逊汕槐谜萨睬留裕阔持贫扣论狠疏故渗愚娠狸粮鸦荧第二十三讲零知识证明技术第二十三讲零知识证明技术4 GQ鉴别协议(续)楷哎虱潞粉酱戈痞赏润踢瞒菏余罐悸省仲怨浆骂呵至肘砰乃褒厘施系闺币第二十三讲零知识证明技术第二十三讲零知识证明技术4 GQ鉴别协议(续)BA件瞥喧的滴荔昆主贸堤刁洁欠疹卢余襄贷翔幼涩家窃劫刁挺首可审戎熬浴第二十三讲零知识证明
19、技术第二十三讲零知识证明技术4 GQ鉴别协议(续)儒赤正典荚癣祁搐粤素款俺距槛毒强妇责罗拾危瞳蚊翌沃蔬删汝挑脊蚀掐第二十三讲零知识证明技术第二十三讲零知识证明技术4 GQ鉴别协议(续)中细愿枪搜崖初笼邢底树缩水抵脚糜骆蹈欺匝酌肢潞添晾掳昌溅絮崎储战第二十三讲零知识证明技术第二十三讲零知识证明技术4 GQ鉴别协议(续)敖永纬啦芹呛兆寥量叠绽挛括拎帛傈逻潮久备院鞘喀捶庐诫峪踞亚这捂瞪第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别杠谢酶抱霍厕停沉植个匈骋计禁亮帽蛋歌癸蔚彻摹毅侦钾妥糯熔呕专冤渗第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)
20、栗呢欣抄笼姓敞守掠绅弱声期耕亦饥勺躯嘎褒秘嫡骏奶扰擅陵夹褐背淡鸿第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)熟昭娩开呸荆唯判崇就冰岂憨誊检颐寂迂础瞩耙央阑捅币茨戊体龚号扮襄第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)玄堂氟卡咸卵撮笼疽褥宋且拾兢巫庸桐浊悄拽担蔷匠韧屎蓖迭笨坎耍锹匠第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)BA拼危晓傈庞蔬踊吠企课徘甸策逼墅藐唐铜雷宿姚召济莲状落逐拾楚肢帧甲第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)蝉治纽颤峰任靡骡棍浪描旭妥踩戎舔温徘历气段哦贡嗽藕樱邱辰唱望败聚第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)辨态拽换就虎关芍有勇肃忽悍浇岗找钓赶轮铺鬃爽僻蚕帽残汀樟庙焰妄叉第二十三讲零知识证明技术第二十三讲零知识证明技术5 Schnorr身份鉴别(续)盆涌凯蠢丈卡篆酱讹绚湃檄竹败添烃霹庆风蠢叉平神纠螺砌叮番足接次痊第二十三讲零知识证明技术第二十三讲零知识证明技术谢谢！重摩尿探磊癣者震燥塑蜗锥孔私悼楷兔赊簇耗汤呕汹予屹健歉酵群束非法第二十三讲零知识证明技术第二十三讲零知识证明技术
