文档介绍：11-高级密码协议
Diffie-Hellman problem
Given an element g and the values of gx and gy, what is the value of gxy ?
Computa
（2）Alice将y送给Bob；
（3）Bob猜测x是偶数或奇数，并将猜测结果发给Alice；
（4）如果Bob的猜测正确，抛币结果为正面; 如果Bob的猜测错误，则抛币的结果为反面。Alice公布此次抛币的结果，并将x发送给Ｂob；
（5）Bob确信y=f（x）。
三方智力***
Alice、Bob和Carol都产生一个公钥/私钥密钥对。
加密可交换性质, 即mk1,k2=mk2,k1
Alice产生52个消息(可验证的唯一的随机串)，每个代表一副牌中的一张牌。Alice用她的公钥加密所有这些消息，并将它们发送给Bob。
Bob，由于不能阅读任何消息，他随机地选择5张牌。他用他的公钥加密，并把它们回送给Alice。Bob将余下的47张牌送给Carol。
Carol，由于不能阅读任何消息，也随机选5个消息。她用她的公钥加密，并把它们送给Alice。
-
Alice也不能阅读回送给她的消息，她用她的私钥对它们解密，然后送给Bob或Carol（依据来自谁而定）。
Bob和Carol用他们的密钥解密并获得他们的牌。
Carol从余下的42张牌中随机取5张，把它们发送给Alice。
Alice用她的私钥解密消息获得她的牌。
在游戏结束时，Alice，Bob和Carol都出示他们的牌以及他们的密钥，以便每人都确信没有人***。
百万富翁问题
百万富翁问题
两个百万富翁想知道谁更富有，但不想泄露有关财富多少的任何信息。
如果不借助于第三方，他们自己能做到吗？
“ Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation? ” --- [Yao82]
网络游戏问题：从 [Gold87]演绎
军棋(暗棋)
普通军棋需要第三人为裁判
网络军棋使用服务器(可信第三方)为裁判
? 能否避免使用第三方
*专利：自裁判军棋
自裁判军棋
此军棋可实现不用裁判即可下暗棋的功能，
能达到与网络军棋相同的效果
?id=3218&random=.2393
专利样本
年龄比较
概念
假设A、B年龄a, b，且无意于撒谎
准备适当多的(比如100个)信封顺序排好
B回避，A把前a个信封中做记号
A回避，B把第b个信封取出，把其余信封收起来
A和B共同打开此信封，有记号则说明a>=b，无记号则b>a
比较是否相等
a. 比较两个大文件是否等同
比如网络文件共享或同步，避免传输而比较两个大文件内容是否一致(BT/eMule)
方法是比较两个文件的Hash值
(如果不想泄露自己大文件的Hash值，归为b)
b. 比较两个小文件(短消息)
不能公布内容，也不能公布Hash值
如果公布其Hash值，则容易受到枚举攻击
参见 《应用密码学》 保密的多方计算-协议#3”保密的多方计算约会服务（Secure Multiparty Computation Dating Service） ”
求和/平均值
一群人怎样才能计算出他们的平均薪水，而又不让任何人知道其他人的薪水呢？
Alice在她的薪水上加一个秘密随机数，然后把它送给Bob
Bob把他的薪水加上，并把它送给Carol。
Carol把她的薪水相加，并把它送给Dave。
Dave把他的薪水相加，并把它送给Alice。
Alice减去那个随机数以恢复每个人薪水之总和。
Alice把这个结果除以人数(4)，并宣布结果。
to check if they love each other
Alice有保密输入a，Bob有保密输入b:
a := 1 若A喜欢B / 否则0
b := 1 若B喜欢A / 否则0
目标(在尽可能保护隐私的前提下)计算 f(a,b) := a ^ b
保护隐私的效果
如果f(a,b)=1，则没有隐私
如果f(a,b)=0，则如果对方是0则其不知道自己是否是1，即保护了自己的隐私。
SMPC问题定义
参与者Pi持有输入Xi
计算函数