第十二章安全多方计算课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十二章安全多方计算,*,第十二章安全多方计算,2024/10/3,第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,David Chaum的密码学家晚餐问题,场景描述,三个密码学家(,Alice Bob Carol,)坐在他们最喜欢的三星级餐馆准备吃晚餐,业务逻辑,侍者通知他们晚餐需匿名支付账单,其中一个密码学家可能正在付账,可能已由美国国家安全局,NSA,付账,他们彼此尊重匿名付账的权利，但又需要知道是不是NSA在付账,系统目标,如何确定三者之一在付账同事又要保护付账者的匿名性？,第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,David Chaum的密码学家晚餐问题,一个简单有效的解决方案,每个密码学家将菜单放置于左边而互相隔离开来,每个人只能看到自己和右边密码学家的结果,每个密码学家在他和右边密码学家之间抛掷一枚硬币,每个密码学家广播她能看到的两枚硬币是同一面还是不同的一面,如果有一个密码学家付账，则他说相反的结果,判定结果,桌上说“不同”的人数为奇数某个密码学家在付账,桌上说“不同”的人数为偶数,NSA,在付账,如果某个密码学家在付账，另两人不能,精确定位,到该密码学家,第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,假设密码学家,Alice,试图弄清其他哪个密码学家在付账,如果她看见两个不同的硬币,那么另外两个密码学家或者都说“相同”、或者都说“不同”,付账者是最靠近与未看见的硬币不同的那枚硬币的密码学家,如果她看见两个相同的硬币,那么另外两个密码学家一个说“相同而另一个说“不同”,如果未看见的硬币与她看到的两枚硬币相同,说“不同”的密码学家是付账者,如果未看见的硬币与她看到的两枚硬币不同,说“相同”的密码学家是付账者,第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,假设密码学家,Alice,试图弄清其他哪个密码学家在付账,无论如何,Alice,都需要知道,Bob,与,Carol,抛掷硬币的结果,Crypt,(,i,),Coin,(,i,)分别表示密码学家和掷币结果,Crypt,(,i,)付款输出=,Coin,(,i-,1),Coin,(,i,),Crypt,(,i,)没付款输出=,Coin,(,i-,1),Coin,(,i,),1,第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,Crypt,(0),Crypt,(1),Crypt,(2),Coin,(0),Coin,(2),Coin,(1),第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,“晚餐问题”的延伸,两个密码学家的“晚餐问题”协议,他们会知道谁付的账,旁观者只知道其中某个人付账或者,NSA,付账，不能,精确定位,任意数量的密码学家“晚餐问题”协议,全部坐成一个圈并在他们中抛掷硬币,第十二章安全多方计算,安全多方计算：,密码学家晚餐问题,“晚餐问题”的应用,匿名消息广播,用户把他们自己排进一个逻辑圆圈,构造饭桌,在一定的时间间隔内，相邻的每对用户对他们之间抛掷硬币,使用一些公正的硬币抛掷协议防止窃听者,在每次抛掷之后每个用户说“相同”或“不同”,无条件的,发送方和接受方,不可追踪性,恶意的参与者不能读出报文，但他能通过在,第三步撒谎,来破坏系统,第十二章安全多方计算,安全多方计算：,平均工资问题,平均工资问题,场景描述,Alice,、,Bob,、,Carol,和,Dave,四人在一起组织工作,业务需求,他们想了解平均工资,无仲裁者,系统目标,任何人不想让其他人知道自己的工资,第十二章安全多方计算,安全多方计算：,平均工资问题,平均工资问题的一种有效解决方案,Alice,生成一个随机数，将其与自己的工资相加，用,Bob,的公钥加密发送给,Bob,Bob,用自己的私钥解密，加进自己的工资，然后用,Carol,的公钥加密发送给,Carol,Carol,用自己的私钥解密，加进自己的工资，然后用,Dave,的公钥加密发送给,Dave,第十二章安全多方计算,安全多方计算：,平均工资问题,平均工资问题的一种有效解决方案,Dave,用自己的私钥解密，加进自己的工资，然后用,Alice,的公钥加密发送给,Alice,Alice,用自己的私钥解密，减去原来的随机数得到工资总和,Alice,将工资总和除以人数得到平均工资，宣布结果,协议假定所有的参与者是诚实的，如果不诚实则平均工资错误,Alice,可以谎报结果（她作为了“,名义上,”的集成者）,第十二章安全多方计算,安全多方计算：,平均工资问题,平均工资问题的一种有效解决方案,比特承诺,可以解决“,Alice,谎报,”缺陷,运用比特承诺协议让,Alice,向,Bob,传送他的随机数,协议结束后，,Bob,可以获知,Alice,的工资,第十二章安全多方计算,安全多方计算：,终身伴侣问题,终身伴侣问题,场景描述,Alice,、,Bob,都在寻找终身伴侣,相亲(,非诚勿扰、我们约会吧,),业务需求(,兴趣爱好,),Alice,：KTV、逛街、劲乐团,Bob,：NBA、足球、聚会、宅,系统目标,对自己的择偶要求难为情含蓄表达、意会、不表达,找一个趣味相投的终身伴侣,第十二章安全多方计算,安全多方计算：,终身伴侣问题,终身伴侣问题的一种有效解决方案,使用一个单向函数，,Alice,将她的择偶要求,m,，,HASH,得到一个8位数字的字符串,h,(,m,),Alice,用这8位数字作为电话号码拨号，并留言,如果电话号码无效，,Alice,给这个电话号码申请一个单向函数直到她找到一个与她有相同择偶要求的人,Alice,告诉,Bob,她为她的择偶要求申请一个单向函数的次数,Bob,用和,Alice,相同次数的,HASH,他的择偶要求,他也用这个8位数字作为电话号码，试图听取留言,有留言，则配对成功,第十二章安全多方计算,安全多方计算：,终身伴侣问题,终身伴侣问题的一种有效解决方案,Bob,可以进行“,选择明文攻击,”,可以HASH一般的择偶要求,拨打所得的电话号码，以窃听留言,只有在不可能得到足够多的明文消息的情况下该协议安全,第十二章安全多方计算,安全多方计算：,其它几个经典应用场景,示例一,Alice,认为自己得了某种遗传疾病，想验证自己的想法,她知道,Bob,有一个关于疾病的DNA模型的数据库,如果她把自己的DNA样品寄给,Bob,Bob,可以给出她的DNA的诊断结果,Alice又不想别人知道这是她的隐私,第十二章安全多方计算,安全多方计算：,其它几个经典应用场景,示例二,A,公司决定扩展在某些地区的市场份额来获取丰厚的回报,A,公司也注意到,B,公司也在扩展一些地区的市场份额,两个公司都不想在相同地区互相竞争,信息的泄露可能会导致公司很大的损失,比如另一家对手公司知道A和B公司的扩展地区，提前行动占领市场,又比如房地产公司知道A和B公司的扩展计划，提前提高当地的房租等等,在不泄露市场地区位置信息的情况下知道市场是否有重叠,第十二章安全多方计算,安全多方计算：,其它几个经典应用场景,示例三,两个金融组织计划为了共同的利益决定互相合作一个项目,每个组织都想自己的需求获得满足,他们的需求都是他们自己专有的数据，没人愿意透露给其它方，甚至是“信任”的第三方,那么他们如何在保护数据私密性的前提下合作项目呢？,第十二章安全多方计算,安全多方计算：,基本概念,多方计算问题,一组参与者希望共同计算某个约定的函数,函数的输入参数有多个,每个参与者提供函数的一个输入,安全多方计算问题(,Secure Multi-party Computation,),引入安全因素,其中每个人都知道这个函数的值,除了函数的输出外，没有人知道关于任何其它成员输入的任何事情,第十二章安全多方计算,演讲完毕，谢谢听讲,!,再见，see you again,3rew,2024/10/3,第十二章安全多方计算,