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