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