PPT《第二十二讲 秘密分享与游戏》

4 电话投币协议 4.1 应用实例 一个朋友没有意识到Alice和Bob不在一个地方,留给他们了一辆汽车.他们将怎样决定汽车的归属呢?Bob打个电话给Alice建议由他投币来决定.Alice说选择"背面",但Bob说我投出的是"正面".于是车归了Bob.这里Alice完全有理由怀疑Bob的诚实.下一次,她可能选择别的办法决定这一问题. 4.2 一个解决方法 这里有一个思路,就是Alice随机的选择一个比特b1发给Bob, Bob也随机的选择一个比特b2发给Alice,投币的结果就是b1 ? b2.问题就是随先发送,如果Alice先,Bob将可以选择b2来控制投币的结果.这并不公平. 4.3 公平投币的要求 (1) Bob必须在听到Alice猜测之前就已经投币. (2) Bob不能够在听到Alice猜测之后重复投币. (3) Alice不能在其猜测之前得到投币结果. 4.4 使用平方根的投币 Alice Bob 4.4 使用平方根的投币(续) 4.4 使用平方根的投币(续) 4.4 使用平方根的投币(续) 4.4 使用平方根的投币(续) 4.4 使用平方根的投币(续) 4.4 使用平方根的投币(续) 5电话扑克协议 一个类似于公平投币的协议就是电话扑克协议,它允许Alice和Bob在电话两端玩扑克.不同于处理"正面"和"反面"两条消息,Bob需要处理分别代表每一张牌的52个数字c1, c2,..., c52 .如何保证在游戏中没有欺诈? 5.1 思想 Bob用自己的加密密钥加密牌c1,c2,..., c52发送给Alice.Alice随机选择5张牌,用自己的加密密钥加密,发还给Bob. Bob解密这些牌后发还给Alice,她再解密决定自己手中的5张牌. Alice再随机选择5张牌发给Bob. Bob解密它们得到自己的5张牌. 5.1思想(续) 在游戏的过程中,剩下的牌可以按照同样的方法发出.在游戏结束后,Alice和Bob都公布自己的牌和密钥对以确定没有人在游戏中欺骗. 5.2 基于离散对数的扑克 5.2 基于离散对数的扑克(续) Alice Bob 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 5.2 基于离散对数的扑克(续) 谢谢!