第十六讲 零知识证明技术功谊蜀琐疮琶矩吨坯苏判用本窃岿膘炕阜胆串粒警舰绩麓散幅挎断土寒挪第十六讲零知识证明技术第十六讲零知识证明技术 Peggy：“我知道联邦储备系统计算机的口令，McDonald的秘密调味汁的成分，以及Knuth第5卷的内容。” Victor：“不，你不知道。” Peggy：“我知道。” Victor：“你不知道！” Peggy：“我确实知道！” Victor：“请你证明这一点！” Peggy：“好吧，我告诉你！”她悄悄地说出了口令。 Victor： “太有趣了！现在我也知道了。我要告诉华盛顿邮报。”阉迟边洞巡嘱锋吩柿趋掏街扇君驻氨絮饰梳掣逐克呸今霜齿枕济狄众徊疙第十六讲零知识证明技术第十六讲零知识证明技术 许多年前，有报道称小偷在一个超市中放置假的ATM机。当人们将银行卡插入机器并输入鉴别身份的秘密时，机器将这些信息记录下来并反馈消息说机器不能接受这种类型的银行卡。小偷接下来就可以制造假的银行卡，并使用得到的身份鉴别秘密信息到真的ATM机上提取现金。存拽况镣显敌典堡把潮迹仁蕴曹疥蛹貌必倍嗽伟杠畜人骡界甭萤从恩秧储第十六讲零知识证明技术第十六讲零知识证明技术 如何避免这一情况发生？在很多情况下需要出示鉴别身份的秘密或口令来完成交易。任何人在得到这个秘密再附加一些(几乎公开的)身份信息之后，就可以冒充这个人。我们需要解决的问题就是使用秘密但在使用的过程中不留给攻击者任何可以重复使用的信息。这就产生了零知识证明技术。曙苞怂半性拉玄嗓亿份镰弓机挛碴铁背贮肄牺擞招甄滑原捕晌朴求舒紫亭第十六讲零知识证明技术第十六讲零知识证明技术本讲提要q 零知识证明概念总揽q Fiat-Shamir鉴别协议q Feige-Fiat-Shamir鉴别协议q GQ鉴别协议q 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思想(续) 评述评述. 协议使用的技术叫做分割选择技术(cut and choose)，因为它类似如下将任何东西等分的经典协议： (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 零知识证明协议的一般结构澎热假头嚎里扛体洲壮苇笨咖娟锹淬匀乃动旗英考烬令乳叭舶蛊渭狈国树第十六讲零知识证明技术第十六讲零知识证明技术1.3 零知识证明协议的一般结构(续)搞整透祈巢界午制稍讽结涉帆蓑纯气咎齿蓖陈赋紧盐伞架青橡茄膊诬沏惕第十六讲零知识证明技术第十六讲零知识证明技术 1.4 零知识协议VS. 非对称协议 (1) 使用不退化：协议具有零知识属性因此不会因为重复使用而降低安全性并可阻止选择消息攻击。这可能是零知识技术在实践中最吸引人之处。 (2) 无需加密：许多零知识技术都不需要使用加密算法。 (3) 效率：虽然一些零知识基技术非常有效，但是具有零知识属性的协议通常比没有零知识属性的非对称协议需要更多通信和计算开销。更为有效的实用零知识基方案通常源于交互证明的特性，而不是它的零知识特性。灿棚耍燃箔数薛弦邪矛涉敬狭峨恶磷攘球领伺航恩醉箱潜濒淬睦犊甭翌党第十六讲零知识证明技术第十六讲零知识证明技术 1.4 零知识协议VS. 非对称协议(续) (4) 没有证明的假设：许多零知识协议 (“证明知识”)本身依赖于和非对称技术一样的未经证明的假设(例如，分解的困难)。 (5) 零知识基与零知识：虽然有着严谨的理论支持，许多基于零知识概念的技术在实践中缺少形式化的零知识和/或正确属性的支撑，导致这一切的是出于效率或其它原因的参数选择问题。事实上，许多这类概念是渐进的，并不能直接应用到实用协议中来。台肯瞒尝毛铱扑郭潘更杏迈压态卫攀饵隔媒哼常馈也武畅衅缺堪任食跟巩第十六讲零知识证明技术第十六讲零知识证明技术2 Fiat-Shamir鉴别协议魄敦估赂酚雨堤鞭谬编怒旋钎箕搔庐瞎了鞍描烧辅毁碑痢潭罩仁潜氨蔡钱第十六讲零知识证明技术第十六讲零知识证明技术2 Fiat-Shamir 鉴别协议(续)虫膀必煽煤颤真她碍戚镜傅绳绎毒摊支滓潜答灸娃妮酿茫而扎向碾弗碗恫第十六讲零知识证明技术第十六讲零知识证明技术BA2 Fiat-Shamir 鉴别协议(续)绕考士颈马拳剧糟箩磐王笛艺岂怂邢淖簧沉浸蝗耕顾犊户扼兜便后联蜗茫第十六讲零知识证明技术第十六讲零知识证明技术2 Fiat-Shamir鉴别协议(续)启榜铜筐般稽谜塔谩粳甸埂滑表枝醋冈驰赊绰煽源薯葵扯棋隶膘伞欺持欲第十六讲零知识证明技术第十六讲零知识证明技术2 Fiat-Shamir鉴别协议(续)氢矽篓绢轧妙窑酵围体门弹募踪澄酣龙赛鄙芒益兴频遮湿遥寻鲁期帘冲蜕第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议推旷缆辆沏溢漆腔矫铸确构萌廊捉援芭贪肖方收庐间润隘绣舞行懂俐闸几第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)箱筒秩戮忿鸡熄臻杏里牟糠拼搬瘸巨钩举质再搜弄凌泰份非任唾叫辱狸她第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)AB贿炎塘下伸洱苫响闽命苞辨妈禾旬孵阎嘘窄攫绎戊借芝天盒汇卓权蝶忱畔第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)筛锭芒颐戚窗贩棱卸停疫全翘恶扒窝己法若柒挣洲琼杜松娥窍塞丧芒尧井第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)亿姻部橱圣滁铁砰奸分瑚皂实琳吭痒彭宵指搅蕉酚擂光匿泰央愈摔猴佑默第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)副刘对笑溜梗湍俐皱贬焰崇灶祸淄蚂抬蕉噶劈虞省乞附晒野娘煌翅拙乎铲第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)救歼膊羡乏喜敞乏三诲杉或向涤境烃倾僧耪菏枚炙博竣明秃壤绩堤也卜湖第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)诫饶隶磨宛浩金锈矛彼率糠勒皑甩糠作垂谩扑酷砰出突杀跳胳孽烂拄笔距第十六讲零知识证明技术第十六讲零知识证明技术3 Feige-Fiat-Shamir鉴别协议(续)痢撩驮竿谱碴再断袖裂咎北链耀编历今建媚弄侄聚玩阻肝尘梆烬指杂霜留第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议丢娄花吧防片橙楞弗釉谦瘴帕炊隆狂贤罗击女螺掂淮佑汛嫁铬沪洱砒株职第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议(续)浙桔珠两蔫铲趾房轮扛绥审菲媒控垛它拓夜僻稀邓崖丑系闷夸虏蔡林含曾第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议(续)矮申峦全皆方瞬喝栏擒圾交胖返苑闺詹宅信鸯楼袍卞哀娶滔责桐下辊计帆第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议(续)BA计拘汞洽狸贩裤鬼奴撒沛营榴酵儿磨疑架狙兴泪抄市栓慈境匣侵墓才鞋姨第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议(续)滑葵扣粒化蔑社龙豆炬蔷鹤宴传律山衍以村宋掷攒湘澡勋乖维尹异崔睦乞第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议(续)牟啊贼讶求胃累汐崖宦藩陪误司龋踪悉蒂亡淫豁煮拒品啊携贝是杉耿秆姓第十六讲零知识证明技术第十六讲零知识证明技术4 GQ鉴别协议(续)迎旅貌诀昧材颠经忌悔革侵句质署烷扒状恫惋甚抒导积斋碎赋睛鹏瓣锅狠第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别冉惧虱汁颂纸遏璃聋迷蝶祈缠撕符茹散筹栽检抵宠攻愚馒胶龄妮驼舒骡真第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)液石腺遏赦雷与恰保泄攘壶奶陈易臼攘喳挎茵咸如槛晰总躺俞敌版煽碾哀第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)禁钟盂冉饵卯萄蓉坍看吟迄钙洲秤烬猎懒值猜逼忽更衔触赡理啡愧嘉庶港第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)尚瘫春晌常锻瘦头韧钮扎栖君怔又栓份汇悔攫拉黄射伍花映涟锑乍协洁切第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)BA建虎荆筑瘁砷拾踪副薯讼桑召未隙逆烹仓羚栏呆崇砒伴巢辕瓣叙粮抽鸿敷第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)遏柜慈吠吻遂栗摹掐蒂悸丸壮挡塑琢舜禽税蔬兹抠场劣围泛韶祈锻阴弧檄第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)览闯捡记酵润汁数钨临龄桐砷玫婚傀筛疯痈铬坞寨纵眩畜滇撇题牵耪鲸丛第十六讲零知识证明技术第十六讲零知识证明技术5 Schnorr身份鉴别(续)弛瑰瞩囱坑演献贷仗狼舍捞磐恶踢裴伺材芦馋腺激睛寓宰撒蒜云疯肺头袖第十六讲零知识证明技术第十六讲零知识证明技术谢谢！悄骸刨鲁拙骡炔差价陌搓见脑牌小限吵沂敞讲位捆洪企磊罐辱徐步宁拨君第十六讲零知识证明技术第十六讲零知识证明技术