5.5 不经意传输

    密码员Bob正在拼命地想将一个500比特的数n进行因子分解。他知道它是5个100比特的数的乘积，但不知道任何更多的东西。（这是一个问题。如果他不能恢复这个密钥，他就得加班工作，势必错过他和Alice每周一次的智力扑克游戏。）

    你知道什么？现在Alice来了：

    “我碰巧知道那个数的一个因子，”Alice说，“并且我要一百美元才把它卖给你。那是一比特一美元。”为了表明她的诚意，她使用一个比特提交方案并分别提交每一比特。

    Bob很感兴趣，但他只有50美元。Alice又不愿降价，只愿意以一半的价格卖给Bob一半的比特。“这将会节省你相当多的工作，”她说。

    “但是我怎么知道你的数确实是n的一个因子呢？如果你给我看那个数并让我验证它是一个因子，那么我将同意你的条件”， Bob说。

    他们陷入了僵局。Alice不能在不透露n的情况下让Bob相信她的数是n的一个因子，而Bob也不愿买一个可能毫无用处的数的50比特。

    这个借自Joe Kilian[831]的故事，介绍了不经意传输的概念。Alice传送一组消息给Bob，Bob收到了那些消息的某个子集，但Alice不知道他收到了那些消息。然而这并没有彻底解决上面的问题。在Bob收到那些比特的任意一半后，Alice就还得用一个零知识证明来使他相信她发送的那些比特是n的部分因子。

    在下面的协议中，Alice将发送给Bob两份消息中的一份。Bob将收到其中一条消息，并且Alice不知道是哪一份。

        （1）Alice产生两个公开密钥/私钥密钥对，或总共四个密钥。她把两个公开密钥发送给Bob。

        （2）Bob选择一个对称算法（例如DES）密钥。他选择Alice的一个公开密钥并用它加密他的DES密钥。他把这个加了密的密钥发送给Alice，且不告诉她他用的是她的哪一个公开密钥加密的DES密钥。

        （3）Alice解密Bob的密钥两次，每次用一个她的私钥来解密Bob的密钥。在一种情况下，她使用了正确的密钥并成功地解密Bob的DES密钥。在另一种情况下，她使用了错误的密钥，只是产生了一堆毫无意义，而看上去又象一个随机DES密钥的比特。由于她不知道正确明文，故她不知道哪个是正确的。

        （4）Alice加密她的两份消息，每一份用一个不同的在上一步中产生的DES密钥（一个真的和一个毫无意义的），并把两份消息都发送给Bob。

        （5）Bob收到一份用正确DES密钥加密的消息及一份用无意义DES密钥加密的消息。当Bob用他的DES密钥解密每一份消息时，他能读其中之一，另一份在他看起来是毫无意义的。

    Bob现在有了Alice两份消息中的一份，而Alice不知道他能读懂哪一份。很遗憾，如果协议到此为止，Alice有可能进行欺骗。另一个步骤必不可少。

        （6）在协议完成，并且知道了两种可能传输的结果后，Alice必须把她的私钥给Bob，以便他能验证她没有进行欺骗。毕竟，她可以用第（4）步中的两个密钥加密同一消息。

    当然，这时Bob可以弄清楚第二份消息。

    因为Alice无法知道两个DES密钥中的哪一个是真的，故这个协议能防止Alice的攻击。她加密两份消息，但Bob只能恢复出其中之一¾¾一直到第（6）步。它同样能防止Bob的攻击，因为在第（6）步之前，他没有办法得到Alice的私钥来确定加密另一份消息的DES密钥。这可能看起来仍不过象一个较复杂的通过Modem掷硬币的方法，但当把它用于较复杂的协议时，它具有广泛的意义。

    当然，没有办法阻止Alice发送给Bob两份完全无用的消息：“Nyah nyah”和“You sucker”。这个协议确保Alice发送给Bob两份消息中的一份；它不保证Bob想收到其中的任何一份。

    在文献中还有其他的不经意传输协议。其中有些是非交互式的，即Alice可以公布她的两份消息，并且Bob只能收到其中一份。他能自己做此事，不必与Alice通信[105]。

    没有人真正注意实际中能否进行不经意传输，但这个概念却是其它协议的重要构成部分。尽管有许多种不经意传输——我有两个秘密你得到一个；我有n个秘密你得到一个；我有一个秘密你可能得到其中的1/2；等等——它们都是等价的[245，391，395]。