安全多方计算课件

1、安全多方计算1 第十二章第十二章 安全多方计算安全多方计算 安全多方计算2 安全多方计算：密码学家晚餐问题密码学家晚餐问题 oDavid Chaum的密码学家晚餐问题的密码学家晚餐问题 n场景描述场景描述 o三个密码学家(Alice Bob Carol)坐在他们最喜欢的三星级餐馆准备吃晚餐 n业务逻辑业务逻辑 o侍者通知他们晚餐需匿名支付账单 n其中一个密码学家可能正在付账 n可能已由美国国家安全局NSA付账 他们彼此尊重匿名付账的权利，但又需要知道是不是NSA在付账 n系统目标系统目标 o如何确定三者之一在付账同事又要保护付账者的匿名性？ 安全多方计算3 安全多方计算：密码学家晚餐问题密码学

2、家晚餐问题 oDavid Chaum的密码学家晚餐问题的密码学家晚餐问题 n一个简单有效的解决方案一个简单有效的解决方案 o每个密码学家将菜单放置于左边而互相隔离开来 n每个人只能看到自己和右边密码学家的结果 o每个密码学家在他和右边密码学家之间抛掷一枚硬币 o每个密码学家广播她能看到的两枚硬币是同一面还是不同的一面 n如果有一个密码学家付账，则他说相反的结果 o判定结果 n桌上说“不同”的人数为奇数某个密码学家在付账 n桌上说“不同”的人数为偶数NSA在付账 n如果某个密码学家在付账，另两人不能精确定位到该密码学家 安全多方计算4 安全多方计算：密码学家晚餐问题密码学家晚餐问题 o假设密码学

3、家假设密码学家Alice试图弄清其他哪个密码学家在付账试图弄清其他哪个密码学家在付账 n如果她看见两个不同的硬币如果她看见两个不同的硬币 o那么另外两个密码学家或者都说“相同”、或者都说“不同” n付账者是最靠近与未看见的硬币不同的那枚硬币的密码学家 n如果她看见两个相同的硬币如果她看见两个相同的硬币 o那么另外两个密码学家一个说“相同而另一个说“不同” n如果未看见的硬币与她看到的两枚硬币相同 说“不同”的密码学家是付账者 n如果未看见的硬币与她看到的两枚硬币不同 说“相同”的密码学家是付账者 安全多方计算5 安全多方计算：密码学家晚餐问题密码学家晚餐问题 o假设密码学家假设密码学家Alic

4、e试图弄清其他哪个密码学家在付账试图弄清其他哪个密码学家在付账 n无论如何Alice都需要知道Bob与Carol抛掷硬币的结果 oCrypt(i),Coin(i)分别表示密码学家和掷币结果 nCrypt(i)付款输出 = Coin(i-1) Coin(i) nCrypt(i)没付款输出 = Coin(i-1) Coin(i) 1 安全多方计算6 安全多方计算：密码学家晚餐问题密码学家晚餐问题 Crypt(0) Crypt(1)Crypt(2) Coin(0) Coin(2) Coin(1) 安全多方计算7 安全多方计算：密码学家晚餐问题密码学家晚餐问题 o“晚餐问题晚餐问题”的延伸的延伸 n两

5、个密码学家的两个密码学家的“晚餐问题晚餐问题”协议协议 o他们会知道谁付的账 o旁观者只知道其中某个人付账或者NSA付账，不能精确定位 n任意数量的密码学家任意数量的密码学家“晚餐问题晚餐问题”协议协议 o全部坐成一个圈并在他们中抛掷硬币 安全多方计算8 安全多方计算：密码学家晚餐问题密码学家晚餐问题 o“晚餐问题晚餐问题”的应用的应用匿名消息广播匿名消息广播 n用户把他们自己排进一个逻辑圆圈 o构造饭桌构造饭桌 n在一定的时间间隔内，相邻的每对用户对他们之间抛掷硬币 o使用一些公正的硬币抛掷协议防止窃听者 n在每次抛掷之后每个用户说“相同”或“不同” 无条件的无条件的发送方和发送方和 接受方

6、接受方不可追踪性不可追踪性 恶意的参与者不能读出报文，但他能通过在恶意的参与者不能读出报文，但他能通过在第三步撒谎第三步撒谎来破坏系统来破坏系统 安全多方计算9 安全多方计算：平均工资问题平均工资问题 o平均工资问题平均工资问题 n场景描述场景描述 oAlice、Bob、Carol和Dave四人在一起组织工作 n业务需求业务需求 o他们想了解平均工资 o无仲裁者 n系统目标系统目标 o任何人不想让其他人知道自己的工资 安全多方计算10 安全多方计算：平均工资问题平均工资问题 o平均工资问题的一种有效解决方案平均工资问题的一种有效解决方案 nAlice生成一个随机数，将其与自己的工资相加，用Bo

7、b的公钥加密发 送给Bob nBob用自己的私钥解密，加进自己的工资，然后用Carol的公钥加密发 送给Carol nCarol用自己的私钥解密，加进自己的工资，然后用Dave的公钥加密 发送给Dave 安全多方计算11 安全多方计算：平均工资问题平均工资问题 o平均工资问题的一种有效解决方案平均工资问题的一种有效解决方案 nDave用自己的私钥解密，加进自己的工资，然后用Alice的公钥加密发 送给Alice nAlice用自己的私钥解密，减去原来的随机数得到工资总和 nAlice将工资总和除以人数得到平均工资，宣布结果 u协议假定所有的参与者是诚实的，如果不诚实则平均工资错误协议假定所有的

8、参与者是诚实的，如果不诚实则平均工资错误 uAlice可以谎报结果（她作为了可以谎报结果（她作为了“名义上名义上”的集成者）的集成者） 安全多方计算12 安全多方计算：平均工资问题平均工资问题 o平均工资问题的一种有效解决方案平均工资问题的一种有效解决方案 n比特承诺比特承诺可以解决可以解决“Alice谎报谎报”缺陷缺陷 o运用比特承诺协议让Alice向Bob传送他的随机数 o协议结束后，Bob可以获知Alice的工资 安全多方计算13 安全多方计算：终身伴侣问题终身伴侣问题 o终身伴侣问题终身伴侣问题 n场景描述场景描述 oAlice、Bob都在寻找终身伴侣相亲相亲(非诚勿扰、我们约会吧非诚

9、勿扰、我们约会吧) n业务需求业务需求(兴趣爱好) oAlice：KTV、逛街、劲乐团 oBob：NBA、足球、聚会、宅 n系统目标系统目标 o对自己的择偶要求难为情含蓄表达、意会、不表达 o找一个趣味相投的终身伴侣 安全多方计算14 安全多方计算：终身伴侣问题终身伴侣问题 o终身伴侣问题的一种有效解决方案终身伴侣问题的一种有效解决方案 n使用一个单向函数，Alice将她的择偶要求m，HASH得到一个8位数字 的字符串h(m) nAlice用这8位数字作为电话号码拨号，并留言 o如果电话号码无效，Alice给这个电话号码申请一个单向函数直到她找到一 个与她有相同择偶要求的人 nAlice告诉B

10、ob她为她的择偶要求申请一个单向函数的次数 nBob用和Alice相同次数的HASH他的择偶要求 o他也用这个8位数字作为电话号码，试图听取留言 n有留言，则配对成功 安全多方计算15 安全多方计算：终身伴侣问题终身伴侣问题 o终身伴侣问题的一种有效解决方案终身伴侣问题的一种有效解决方案 nBob可以进行“选择明文攻击” o可以HASH一般的择偶要求 o拨打所得的电话号码，以窃听留言 n只有在不可能得到足够多的明文消息的情况下该协议安全 安全多方计算16 安全多方计算：其它几个经典应用场景其它几个经典应用场景 o示例一示例一 nAlice认为自己得了某种遗传疾病，想验证自己的想法 n她知道Bo

11、b有一个关于疾病的DNA模型的数据库 o如果她把自己的DNA样品寄给Bob nBob可以给出她的DNA的诊断结果 nAlice又不想别人知道这是她的隐私 安全多方计算17 安全多方计算：其它几个经典应用场景其它几个经典应用场景 o示例二示例二 nA公司决定扩展在某些地区的市场份额来获取丰厚的回报 nA公司也注意到B公司也在扩展一些地区的市场份额 n两个公司都不想在相同地区互相竞争 o信息的泄露可能会导致公司很大的损失 n比如另一家对手公司知道A和B公司的扩展地区，提前行动占领市场 n又比如房地产公司知道A和B公司的扩展计划，提前提高当地的房租等等 n在不泄露市场地区位置信息的情况下知道市场是否

12、有重叠 安全多方计算18 安全多方计算：其它几个经典应用场景其它几个经典应用场景 o示例三示例三 n两个金融组织计划为了共同的利益决定互相合作一个项目 n每个组织都想自己的需求获得满足 o他们的需求都是他们自己专有的数据，没人愿意透露给其它方，甚至是 “信任”的第三方 n那么他们如何在保护数据私密性的前提下合作项目呢？ 安全多方计算19 安全多方计算：基本概念基本概念 o多方计算问题多方计算问题 n一组参与者希望共同计算某个约定的函数 o函数的输入参数有多个 n每个参与者提供函数的一个输入 o安全多方计算问题安全多方计算问题(Secure Multi-party Computation) n引入安全因素 o其中每个人都知道这个函数的值 o除了函数的输出外，没有人知道关于任何其它成员输入的任何事情 安全多方计算20 安全多方计算：基本概念基本概念 o来自于经典应用场景的启发来自于经典应用场景的启发 n安全多方计算的基本特征安全多方计算的基本特征 o两方或多方参与者基于他们