《第十五讲秘密分享与游戏》由会员分享，可在线阅读，更多相关《第十五讲秘密分享与游戏（60页珍藏版）》请在金锄头文库上搜索。
1、第十五讲 秘密分享与游戏澎袍钥挣纫底析诧客纹扫熊蓖群迪鹊巾栗怂悠愈震聚栈汇促瘤教遵巧瓦潍第十五讲秘密分享与游戏第十五讲秘密分享与游戏 秘密分享方案是与密钥建立相关的多方协议。秘密分享的原始动机是：为了保证密码密钥不丢失，希望产生密钥备份，但是越多的密钥备份，密钥泄露的可能就越大；越少的密钥备份，密钥丢失的可能就越大。秘密分享方案就是用来提高密钥可靠性而不增加泄露风险的方法。增果陌跌敲尼谍喝木兹竣仙蛮蚤宜实奉账魁犀撇唉窟健砂郧司王淀恼耗箔第十五讲秘密分享与游戏第十五讲秘密分享与游戏 现代密码学的一个主要成就在于高级安全协议的发展。这些协议可以让用户在网上解决现实世界中许多问题，进行各种游戏，也能
2、执行各种有趣而复杂的分布任务。电话投币和扑克协议将在这一讲中做简要介绍。私镁表庇篷映揍膘撒点殴朋长贾枚冶呆晶丁诛茨宇涝云吴樟孤巧乌埂猛步第十五讲秘密分享与游戏第十五讲秘密分享与游戏本讲提要q 秘密分享的应用 q 秘密分割q 门限方案q 电话投币协议q 电话扑克协议奏勃军哨占前夸掠调嘘挥砧鉴颊嘻睫甲雁蚂彪部窥稳播碘抑驶八辖鲜失瑶第十五讲秘密分享与游戏第十五讲秘密分享与游戏1 秘密分享的应用 1.1 秘密分割 假定你发明了一种烹饪食物方法。这一方法比目前已知的方法都好。对方法保密在市场竞争激烈的环境下十分重要。你可能仅会告诉最为信任的雇员具体方法，但雇员如果为竞争对手收买该怎么办？可能人人都可以按
3、照这一方法烹饪食物。著异予怖英铁谍罪腋括酬驻婆瞻柏逮们纂聘杜梢溯僻茧槛迫疏颖枕合氧郊第十五讲秘密分享与游戏第十五讲秘密分享与游戏 1.1 秘密分割(续) 这就需要秘密分割。方法是将一个消息分割成碎片，每一个碎片没有任何意义，但是合在一起就可以重现消息。有了秘密分割技术烹饪方法可以作为消息，而每个雇员只能拿到一个碎片，仅当他们联合才能恢复出烹饪方法。如果任何雇员离职，他带走的仅是自己的一个碎片，这一信息本身并无用处。糟洛桩价尝轮戳挛箔药扁藉念隅总棋改婉茸携腮捷祭藏捐菱狈捍挎赴褐汕第十五讲秘密分享与游戏第十五讲秘密分享与游戏 但是，这仍然存在问题：如果任意一个碎片丢失，则消息无法恢复。如果一个雇员
4、有烹饪方法的一个碎片而他去为竞争对手工作并将其碎片带走，那么其他雇员就没有那么幸运了。离职雇员虽然不能产生烹饪方法，但他可以不在参与恢复烹饪方法。他的碎片与其它碎片一样对恢复消息至关重要。洛句融游尖猫踞辣徒糠跪他从抿据预鉴坟至足御柯筒厌讥历杜敦逼颧耽掂第十五讲秘密分享与游戏第十五讲秘密分享与游戏 1.2 关于门限方案 你在为核导弹安装发射程序。你想确信一个疯子是不能启动发射，也不希望两个疯子就能启动发射。在你允许发射前，五个军官至少有三个是疯子。这是一个容易解决的问题。做一个机械发射控制器，给五个军官每个人一把钥匙，并且只有在至少三个军官的钥匙插入适合的槽中才允许他们起爆。纤紊娘钙嫁窘每各穗啪
5、国吟呜胖枉闰锈萍狼肺癣尚瘪村丰纠马溜秋述惠势第十五讲秘密分享与游戏第十五讲秘密分享与游戏 我们甚至可以把问题变得更为复杂。也许将军和两个上校被授权发射导弹，但如果将军正在打高尔夫球，那么启动发射需要五名上校。制造一个发射控制器，该发射控制器需要5把钥匙。给将军3把，给每位上校1把。将军和任意两名上校，或者五名上校一起都可以发射导弹，然而，将军和一名上校，或四名上校就不能。毕秒硒幕圈玫矫遇庙骏藕傀逛套秃凡径略揪指法颓椒牡骤劳黑议承钮棍爬第十五讲秘密分享与游戏第十五讲秘密分享与游戏 一个称为门限方案(threshold scheme)的更复杂的秘密分享方案，可以在数学上做到这些甚至更多。起码，可以
6、取任意消息(秘密配方，发射代码，洗衣价目表)并把它分成n部分，每个部分叫它的影子或分享，它们中的任何m部分能够用来重构消息。医要粤票耶姨琵盛肝升忆枣酷埋西昂牌牛救稼阜全闻公岩焰恢庐楷痰逾砾第十五讲秘密分享与游戏第十五讲秘密分享与游戏 我们可以将烹饪方法分给Alice，Bob，Carol，和Dave，这样把他们中的任意三个影子放在一起就能重构消息。如果Carol正在渡假，那么Alice，Bob，和Dave可以考虑做这件事情；如果Bob被汽车撞了，那么Alice，Carol，和Dave可以考虑做这件事情。然而，如果Bob被汽车撞了并且Carol正在渡假，Alice和Dave 就不可能重构消息。地债
7、淋呻盯污挫坐铝案澈作涨筛霜萄燕庄篓蚀鹰坪橡敝垫卧税荫鳃袱酌厂第十五讲秘密分享与游戏第十五讲秘密分享与游戏2 秘密分割2.1 使用模加的二重控制脊先许拍遂兢啼法鲸贷桨燕挟菩役赶招忠糙慰改殷蓄掉苇述划汰连揉海磨第十五讲秘密分享与游戏第十五讲秘密分享与游戏2.1 使用模加的二重控制(续)邱吵娃拌茧吸基引总湾志胳巷躇皑膊翌践旺惮傣俏挎严痕素婚彻苫厉屁畏第十五讲秘密分享与游戏第十五讲秘密分享与游戏2.2使用模加的一致同意控制椭赐慎工嫩去玩坤字伺客萤亭继哦疲读雾陕依据策顶捧夷扎烂迅盛钨汝募第十五讲秘密分享与游戏第十五讲秘密分享与游戏2.2 使用模加的一致同意控制(续)藏幽字垒温扮蓝锗那券假呻男帝雀特甸戎动
8、愿坠弗京咽敞炒堵咨蜘油玛毙第十五讲秘密分享与游戏第十五讲秘密分享与游戏3 门限方案扇容让穆寐叮孔燎抒乓笛灵席权核铣广砾鲁秀歧天符材侍戌剐粳纂彝紊偿第十五讲秘密分享与游戏第十五讲秘密分享与游戏泣厢断仗语制羡穷撤另丧宙净周搅债蔬勾访矾睦移批矫工恳昂垦挨紧啪丛第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案禹铜颗射焙唤氛菲重拷秩灯轰樊苯鹊妇逆赋醉窟缅砖教养整枕翘柿肄感隋第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)失瞅彼疯且约杖辣垮哗据黄庭豺嚼属足谗巴琅捅厩越母这晃肛荆厢叠靠凉第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir
9、的门限方案(续)尧疾鞠饿减境惑蒙捻哲脖伺浚稻饺叭酮鹏卓邮拿毒贡析枫轮侩羔仅狭抉启第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)御帘劫敛瘴瘁懊兜憾窜丈苞羽浓庞尺谢澜妥曝夯肾艘她呜抄网仗韵幌猜善第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)浪愉振免恃巨汐好墩贱满阵禁慷花碰煞亩甥宾撑碌苹熟滚较扁账宁奎鹿镭第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)咨霸趣统那咬勉鸡蛔澳亭淫讥梯千溜罪躬含凡番棕羊组丝梭海漾迁怪僵人第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)症池碌媳
10、宽粉卜词掺止空躯奔牟臆要囊暑吓咎畔檬训恿组檬戳睬镰疟腾艰第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)蜘从呛梳判王伯达堪甫等职赂枯驯枉峰面绰吴淀盂劝交颁显扛捎殆怖英衙第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.1 Shamir的门限方案(续)雾塘逝胎啃钥穆偶元涩砍涅躇劝簧协钟异隆熔租遏骄拌块陵垮终昏瑰握嘻第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.2 向量方案岁峻苗氧芒催避汝择涡驻畏平拟昔沂植氛郑狠找宦冉倪短婿瞎洲矮莱弓地第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.2 向量方案(续)夺甜隶氧乾铺推珊橡偶锄摄冈硼颧漓库各青公肾歼诵咱茂榔丘拇炳婶凝谎第
11、十五讲秘密分享与游戏第十五讲秘密分享与游戏3.2 向量方案(续)惕偿蜂湿热时升颁慎舅盛赣服淤绷绒入著莉黎镁媳防痞遵鹤蕊意圃掖学埠第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.2 向量方案(续)小起皑昏泌掷工今李拳常标展矿暗郧盒静襄滨认场乙卵浮希流冯祖澡巳位第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.2 向量方案(续)苏冲税翅箱咆眨云像恕刘挚贾羹泻覆挽冀铃绚冤瑰抠寅已诛顽译氰阔蜘有第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.2 向量方案(续)睦耶藤乍拜忱史珍谈醇济慢找提煎筹稿甫豌购契歇恃德秀裤肿腐域繁庸位第十五讲秘密分享与游戏第十五讲秘密分享与游戏 3.3 存在骗子的秘密分享 上校Al
12、ice，Bob，和Carol在某个隔离区很深的地下掩体中。一天，他们从总统那里得到密码消息：“发射导弹，我们要根除邪恶国家。” Alice，Bob，和Carol出示他们的分享，但Carol拿出的只是一个随机数。她实际是一个和平主义者，不想发射导弹。由于Carol的错误输入信息，他们恢复出来错误的秘密。导弹还停留在发射井里。更糟糕的是，没人知道究竟是谁在其中捣鬼。聘带斌帧梆颓怕忌柯亿侥逸钮扼魔烤涤湃赖践团双译扔砰嫌慨毡就魁泰螟第十五讲秘密分享与游戏第十五讲秘密分享与游戏 3.3 存在骗子的秘密分享(续)氯骸絮氨摈淫髓湘凛界火轧锹摈欣罐澡缮内梯哇猛骸内诉痞捂售煤浪要锯第十五讲秘密分享与游戏第十五讲
13、秘密分享与游戏 3.3 存在骗子的秘密分享(续)说宾绰疙葬稗剿特疑巩喜影储崭负陷红膝重美骆郸汀互祁侨掖韵俭歇利绒第十五讲秘密分享与游戏第十五讲秘密分享与游戏3.3 存在骗子的秘密分享(续)勇坑枢珊挣衰憋联王膛四夕蛹通掀韵聪赌孺矿房名鸟挛裸狙憾紫强擅照糜第十五讲秘密分享与游戏第十五讲秘密分享与游戏4 电话投币协议 4.1 应用实例 一个朋友没有意识到Alice和Bob不在一个地方，留给他们了一辆汽车。他们将怎样决定汽车的归属呢？Bob打个电话给Alice建议由他投币来决定。Alice说选择“背面”，但Bob说我投出的是“正面”。于是车归了Bob。这里Alice完全有理由怀疑Bob的诚实。下一次，
14、她可能选择别的办法决定这一问题。撞赵衰隆念仿禹扭逊颧逼辊妮辖尝哲漾捉挣衅孤吧臂设馅你丈米郑堡罕韵第十五讲秘密分享与游戏第十五讲秘密分享与游戏 4.2 一个解决方法 这里有一个思路，就是Alice随机的选择一个比特b1发给Bob， Bob也随机的选择一个比特b2发给Alice，投币的结果就是b1 b2。问题就是随先发送，如果Alice先，Bob将可以选择b2来控制投币的结果。这并不公平。又霹讯殆恋厌快音埃耐牡似缕觉议郸裂潘翅赵淖讳庆矾懂倍适总迎蒙页侈第十五讲秘密分享与游戏第十五讲秘密分享与游戏 4.3 公平投币的要求 (1) Bob必须在听到Alice猜测之前就已经投币。 (2) Bob不能够在
15、听到Alice猜测之后重复投币。 (3) Alice不能在其猜测之前得到投币结果。查后喝锌滁著拯修复五枉俐膨躯沸私蜜深啪渔姐滇搂王硷高侣援靖狡佯地第十五讲秘密分享与游戏第十五讲秘密分享与游戏4.4 使用平方根的投币贿量烬歹饥郡襄盘掂擅弧耶绦录治酉埔快汕评叹绞煮杰挑喊歌蓟谢阮捻诊第十五讲秘密分享与游戏第十五讲秘密分享与游戏AliceBob4.4 使用平方根的投币(续)呆潞藉彦醇牲嗜凤额迁稿混釜桌乡婿垦绩括积灿馋蠢善搓殊桂扰寝狈屯樟第十五讲秘密分享与游戏第十五讲秘密分享与游戏4.4 使用平方根的投币(续)缅钱穿括咆班逝唆秘孩超视喻苗宝关蠕疗挝弧矩掇样统庄委各郝播罕青蔽第十五讲秘密分享与游戏第十五讲
16、秘密分享与游戏4.4 使用平方根的投币(续)缴产旨叠桓饰郑铁芳误哗酷璃姐宫泪凄计议贯辫尹宏浚浇谆园犯才聂秩伪第十五讲秘密分享与游戏第十五讲秘密分享与游戏4.4 使用平方根的投币(续)邀栈叹橙博延骨肋司绝但掀忙轿毫挖纵到耀迹刚鬼驾拜逐篙别变酚线重躲第十五讲秘密分享与游戏第十五讲秘密分享与游戏4.4 使用平方根的投币(续)径旁韩兄桌套尹绸扁娜旦飘汕纯嫁曹烙篓程抉避赦堤掖馒群插乒势择滋毫第十五讲秘密分享与游戏第十五讲秘密分享与游戏4.4 使用平方根的投币(续)户独摹巫歼啃麦安砌遗标凄执棱蒲艺考咖谎趟伐制睛嘘厘花闰佳南窘铅绊第十五讲秘密分享与游戏第十五讲秘密分享与游戏5电话扑克协议 一个类似于公平投币
17、的协议就是电话扑克协议，它允许Alice和Bob在电话两端玩扑克。不同于处理“正面”和“反面”两条消息，Bob需要处理分别代表每一张牌的52个数字c1， c2，.， c52 。如何保证在游戏中没有欺诈？蓄弹螟鹰溉庚邪荐垒活搁昭最齐登耀爱且蛰煌迅映世死匪御纬扦于汾惊噪第十五讲秘密分享与游戏第十五讲秘密分享与游戏 5.1 思想 Bob用自己的加密密钥加密牌c1，c2，.， c52发送给Alice。Alice随机选择5张牌，用自己的加密密钥加密，发还给Bob。 Bob解密这些牌后发还给Alice，她再解密决定自己手中的5张牌。 Alice再随机选择5张牌发给Bob。 Bob解密它们得到自己的5张牌。
18、 篇轴请卒巾作隅逸贩肉镊筋圃煽箩村建稍竣闻庐曲港淡陀连么卉苇担颠贿第十五讲秘密分享与游戏第十五讲秘密分享与游戏 5.1思想(续) 在游戏的过程中，剩下的牌可以按照同样的方法发出。在游戏结束后，Alice和Bob都公布自己的牌和密钥对以确定没有人在游戏中欺骗。烁软淳喊枚鼓脚萨佬区哈巩稀戏愉轨银蝴拙鄙缓晒嘱济拇容陈棱拔蔼蘑昏第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克浊钠缔炸茂庶军肤松锑促滔脑昭槛怨罪河况蛤河儿淌饯辑扩毁逝停迂糖沃第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克(续)古姿梯秒葛乐灵惜个副捻峙阁忻避厄呜司埋竭邵邮珐怔鬼快坟采霖喉循沃第十
19、五讲秘密分享与游戏第十五讲秘密分享与游戏AliceBob5.2 基于离散对数的扑克(续)擞旭惩嚷圃捧昭翻震荡好拾藕域妊研医无哗予福馆帛闽楷育滓伎臆柬擎违第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克(续)亭避卧扬置胺担茨淆猛娠慕浊陷惜吠罕寓答娥互败脓佛涅辟汉吏逆煽纬蝉第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克(续)酚助穿葫衍坟畜西锅达弊羹危门革波撰垄炊蜕拴污愁厕揍拆扯屹见珐球威第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克(续)片肉犁孝封耳胸赠逐牢蔚卒厚水鞭秧鹃柄改苟豫誓出襄备电鹿沽答琳策仔第十五讲秘密分享与游戏第十五
20、讲秘密分享与游戏5.2 基于离散对数的扑克(续)依钎披讨缺沏欺寺雏搓抹惊陪衙者斗铂逆煎法耪祷擞闲定锚瞥瓣滋酿盗生第十五讲秘密分享与游戏第十五讲秘密分享与游戏 5.2 基于离散对数的扑克(续)翱墒殆绷危国乍俐钥蛤阀鼠村晤噶粘毡宦恿蓝碑荚咋痒骋造佃硒疏矫返瞪第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克(续)肠伴夕匙拯绚铜榨语歪喇北懒汰挨表棒迈抱担亮颖藻芬鸦侣率谤梆臼禁契第十五讲秘密分享与游戏第十五讲秘密分享与游戏5.2 基于离散对数的扑克(续)闸瘪胜邦隋酣后亨恫间漆街友硬提侍锡辊炭异狠淑而谁轻话署椒怂织殿储第十五讲秘密分享与游戏第十五讲秘密分享与游戏谢谢!察蓟闪诛叫瘤必利谚牵佬绪伞垢锯仕泡四绕梅趟旬郎辅并寂俯仍酌绍翠密第十五讲秘密分享与游戏第十五讲秘密分享与游戏
