4.10 公平的硬币抛掷

    是Joe Kilian[831] 讲故事的时候了：

    Alice和Bob想抛掷一个公平的硬币，但又没有实际的物理硬币可抛。Alice提出一个用思维来抛掷公平硬币的简单方法。“首先，你想一个随机比特，然后我再想一个随机比特，我们将这两个比特进行异或。”Alice建议道。

    “但如果我们中有人不随机抛掷硬币怎么办呢？”Bob问道。

    “这无关紧要，只要这些比特中的一个是真正随机的，它们之异或应该也是真正随机的。”Alice这样回答。经过思考后，Bob同意了。

    没过多久，Alice和Bob碰到一本关于人工智能的书，这本书被丢弃在路旁。 优秀公民Alice说：“我们中有一个必须拣起这本书，并找到一个合适的垃圾箱。”Bob同意并提议用抛币协议来决定谁必须将这本书扔掉。

    “如果最后的比特是‘0’，那么你必须拣取那本书，如果是‘1’，那我必须那样做。”Alice说。“你的比特是什么？”

    Bob答道：‘1’。

    “为什么，我的也是1”Alice顽皮地说“我猜想今天不是你的幸运日。”

    不用说，这个抛币协议有严重的缺陷，真正随机的比特x与任意独立分配的比特y异或仍得到真正随机的比特。Alice的协议不能保证两个比特是独立分布的。事实上，不难验证不存在能让两个能力无限的团体公平抛币的思维协议。Alice和Bob在收到来自密码学方面的一个无名的研究生的一封信后才走出了困境。信上的信息抽象得对任何人都不会有用，但随信用的信封却是随手可得的。

    接下来，Alice和Bob希望抛币，他们对原协议版本进行了修改。首先，Bob确定一个比特，但这次他不立即宣布，只是将它写在纸上，并装入信封中。接下来，Alice公布她选的比特。最后，Alice和Bob从信封中取出Bob的比特并计算随机比特。只要至少一方诚实地执行协议，这个比特的确是真正随机的。Alice和Bob有了这个可以工作的协议，密码学家梦想的社会关系实现了，他们从那以后过得很愉快。

    那些信封很像比特承诺模糊点。当Manuel Blum通过调制解调器引入抛掷公平硬币问题时[194]，他利用比特承诺协议解决了此问题：

        （1）Alice利用在4.9节中所列的任一个比特承诺方案，对一个随机比特承诺。

        （2）Bob试图去猜测这个比特。

        （3）Alice出示这个比特给Bob，如果Bob正确地猜出这个比特，他就赢得了这次抛币。

    一般地，我们需要一个具有如下性质的协议：

        ——Alice必须在Bob猜测之前抛币；

        ——在听到Bob的猜测后，Alice必须不能再抛掷；

        ——Bob在猜测之前必须不能知道硬币怎么落地的。

    有几种方法可用来实现具有这些性质的协议。

采用单向函数的抛币协议

    如果Alice和Bob对使用一个单向函数达成一致意见，协议非常简单：

        （1）Alice选择一个随机数x，她计算y=f（x），这里f（x）是单向函数；

        （2）Alice将y送给Bob；

        （3）Bob猜测x是偶数或奇数，并将猜测结果发给Alice；

        （4）如果Bob的猜测正确，抛币结果为正面;如果Bob的猜测错误，则抛币的结果为反面。Alice公布此次抛币的结果，并将x发送给Ｂob；

        （5）Bob确信y=f（x）。

    此协议的安全性取决于单向函数。如果Alice能找到x和x’，满足x为偶而x'为奇，且y=f（x ）=f（x'），那么她每次都能欺骗Bob。f（x）的没有意义的比特也必须与x不相关。否则，Bob至少某些时候能够欺骗Alice。例如，如果x是偶数，f（x）产生偶数的次数占75%，Bob就有优势。（有时没有什么意义的比特不是在这个应用中使用的最好的比特，因为它可能更易于计算）

采用公开密钥密码的抛币协议

    这个协议既可与公开密钥密码又可与对称密码一起工作。其唯一要求是算法满足交换律，即：

    一般地，对称算法中这个特性并不满足，但对某些公开密钥算法是正确的（例如，有相同模数的RSA算法）。协议如下：

        （1）Alice和Bob都产生一个公开/私钥密钥对。

        （2）Alice产生两个消息，其一指示正面，另一个指示反面。这些消息中包含有某个唯一的随机串，以便以后能够验证其在协议中的真实性。Alice用她的公开密钥将两个消息加密，并以随机的顺序把他们发给Bob，即

EA（M1），EA（M2）

        （3）Bob由于不能读懂其中任意一消息，他随机地选择一个。他用他的公开密钥加密并回送给Alice，即

EB（EA（M））。

M是M1或M2。

        （4）Alice由于不能读懂送回给她的消息，就用她的私钥解密并回送给Bob，即

DA（EB（EA（M）））=EB（M1） 如果M = M1 或

 EB（M2）如果M = M2

        （5）Bob用他的私钥解密消息，得到抛币结果。他将解密后的消息送给Alice

DB（EB（M1）） = M1 或DB（EB（M2）） = M2

        （6）Alice读抛币结果，并验证随机串的正确性。

        （7）Alice和Bob出示他们的密钥对以便双方能验证对方没有欺诈。

    这个协议是自我实施的。任意一方都能即时检测对方的欺诈，不需要可信的第三方介入实际的协议和协议完成后的任何仲裁。让我们试图欺诈，看看协议是如何工作的。

    如果Alice想欺骗，强制为正面，她有三种可能的方法影响结果。首先，她可以在第（2）步中加密两个“正面”的消息。在第（7）步Alice出示她的密钥时，Bob就可以发现这种欺骗。第二种方法，Alice在第（4）步时用一些其它的密钥解密消息，将产生一些乱七八糟的无用信息，Bob可在第（5）步中发现。第三种方法，Alice可在第（6）步中否认消息的有效性，当在第（7）步中Alice不能证明消息无效时，Bob就可以发现。当然，Alice可以在任何一步拒绝参与协议，那样，Alice欺骗Bob的企图就显而易见了。

    如果Bob想欺骗并强制为“反面”，他的选择性不大。他可以在第（3）步中不正确地加密一个消息，但Alice在第（6）步查看最终的消息时就可以发现它。他可以在第（5）步中进行不适当的操作，但这也会导致乱七八糟的无用信息，Alice可在第（6）步中发现。他可以声称由于Alice那方面的欺诈使他不能适当地完成第（5）步的操作，但这种形式的欺诈能在第（7）步中发现。最后，他可能在第（5）步中给Alice一个“反面”的信息，而不管他解密获得的信息是什么，但Alice能在第（6）步中立即检查消息的真实性。

掷币入井协议

    注意到在所有这些协议中，Alice和Bob不能同时知道掷币的结果。每个协议有一个点，在这个点上其中一方（如开始的两个协议中的Alice，最后一个协议中的Bob）知道掷币结果，但不能改变它。然而，这一方能推迟向另一方泄露结果。这被称作掷币入井协议。设想一口井，Alice在井的旁边，而Bob远离这口井。Bob将币扔进井里去，币停留在井中，现在Alice能够看到井中的结果，但她不能到井底去改变它。Bob不能看到结果，直到Alice让他走到足够近时，才能看到结果。

采用抛币的密钥生成

    这个协议的实际应用是会话密钥生成。掷币协议能让Alice和Bob产生随机会话密钥，以便双方都不能影响密钥生成的结果。假定Alice和Bob加密他们的交换，这个密钥生成方法在存在窃听时也是安全的。