4.8 用加密数据计算

    Alice想知道某个函数f（X）对某些特殊的x值的解。不幸的是，她的计算机坏了，Bob愿意为她计算f（x），但Alice又不想让Bob知道她的x。怎样做Alice才能在不让Bob知道x的情况下为她计算f（x）呢？

    这是加密数据计算的一般问题，亦称“对先知隐藏信息”问题。（Bob是先知，他回答问题。）对某些函数来说有许多方法能够解决这个问题，在23.6节中讨论。

4.9 比特承诺

    Alice，这位令人惊异的魔术天才，正表演关于人类意念的神秘技巧。她将在Bob选牌之前猜中Bob将选的牌！注意Alice在一张纸上写出她的预测。Alice很神秘地将那张纸片装入信封中并封上。就在人们吃惊之时Alice将封好的信封随机地递给一观众。“取一张牌，Bob，任选一张”。他看了看牌而后将之出示给Alice和观众。是方块7。现在Alice从观众那里取回信封，并撕开它。在Bob 选牌之先写的预测，也是：方块7！全场欢呼！

    这个魔术的要点在于，Alice在戏法的最后交换了信封。然而，密码协议能够提供防止这种花招的方法。这为什么有用？下面是一个更实际的故事：

    股票经纪人Alice想说服投资商Bob她的选取赢利股票的方法很不错。

    Bob说：“给我选5支股票，如果都赢利，我将把生意给你。”

    Alice说：“如果我为你选了5只股票，你可以自己对他们投资，而不用给我付款。我为什么不向你出示我上月选的股票呢？”

    Bob：“我怎样知道你在了解了上月股票的收益后没改变你上月选择的股票呢？如果你现在告诉我你选的股票，我就可以知道你不能改变他们。在我买你的方法以前我不在这些股票中投资。相信我。”

    Alice：“我宁愿告诉你我上月选择的股票。我不会变，相信我。”

    Alice想对Bob承诺一个预测（即1bit或bit序列），但直到某个时间以后才揭示她的预测。而另一方面，Bob想确信在Alice承诺了她的预测后，她没有改变她的想法。

使用对称密码算法的比特承诺

    这个比特承诺协议使用对称密码：

        （1）Bob产生一个随机比特串R，并把它发送给Alice。

R

        （2）Alice生成一个由她想承诺的比特b组成的消息（b实际上可能是几个比特），以及Bob的随机串。她用某个随机密钥K对它加密，并将结果送回给Bob。

EK（R，b）

    这是这个协议的承诺部分，Bob不能解密消息，因而不知道比特为何。

    当到了Alice揭示她的比特的时候，协议继续：

        （1）Alice发送密钥给Bob；

        （2）Bob解密消息以揭示比特。他检测他的随机串以证实比特的有效性。

    如果消息不包含Bob的随机串，Alice能够秘密地用一系列密钥解密她交给Bob的消息，直到找到一个给她的bit，而不是她承诺的比特。由于比特只有两种可能的值，她只需试几次肯定可以找到一个。Bob的随机串避免了这种攻击，她必须能找到一个新的消息，这个消息不仅使她的比特反转，而且使Bob的随机串准确地重新产生。如果加密算法好，她发现这种消息的机会是极小的。Alice不能在她承诺后改变她的比特。

使用单向函数的比特承诺

    本协议利用单向函数：

        （1）Alice产生两个随机比特串，R1和R2。

R1，R2

        （2）Alice产生消息，该消息由她的随机串和她希望承诺的比特（实际上可能是几比特）组成。

（R1，R2，b）。

        （3）Alice计算消息的单向函数值，将结果以及其中一个随机串发送给Bob。H（R1，R2，b），R1。

    这个来自Alice的传送就是承诺证据。Alice在第（3）步使用单向函数阻止 Bob对函数求逆并确定这个比特。

    当到了要Alice出示她的比特的时候，协议继续：

        （4）Alice将原消息发给Bob。

（R1，R2，b）

        （5）Bob计算消息的单向函数值，并将该值及R1与原先第（3）步收到的值及随机串比较。如匹配，则比特有效。

    这个协议较前面一个的优点在于Bob不必发送任何消息。Alice送给Bob一个对比特承诺的消息，以及另一揭示该bit的消息。

    这里不需要Bob的随机串，因为Alice承诺的结果是对消息进行单向函数变换得到的。Alice不可能欺骗，并找到另一个消息（R1，R2’，b’），满足

H（R1，R2’，b’）=（R1，R2，b）

    通过发给Bob  R1，Alice对b的值作了承诺。如果Alice不保持R2是秘密的，那么Bob能够计算H（R1，R2，b’）和（R1，R2，b），并比较哪一个等于他从Alice那里接收的。

使用伪随机序列发生器的比特承诺

    本协议是更容易的[1137]：

        （1）Bob产生随机比特串，并送给Alice。

RB

        （2）Alice为伪随机比特发生器生成一个随机种子。然后，对Bob随机比特串中的每一比特，她回送Bob下面两个中的一个：

            （a）当Bob比特为0，发生器的输出，或者

            （b）如果Bob的比特为1，发生器输出与她的比特的异或。

        当到了Alice出示她的比特的时候，协议继续：

        （3）Alice将随机种子送给Bob。

        （4）Bob完成第（2）步以确认Alice的行动是合理的。

    如果Bob的随机比特串足够长，伪随机比特发生器不可预测，这时Alice就无有效的方法进行欺诈。

模糊点

    Alice送给Bob以便对比特承诺的这些串有时又叫模糊点。一个模糊点是一个比特序列，虽然在协议中没有说明它为什么必须这样，正如Gilles Brassard所说的，“只要是合理存在的就是有用的”[236]。模糊点有下面四个特性：

    1.Alice能够对模糊点承诺，通过承诺模糊点来承诺一个比特。

    2.Alice能够打开她所承诺的任何模糊点。当她打开模糊点时，她能让Bob相信在她对模糊点承诺时她所承诺的比特值。因此，她不能选择把任何模糊点作为0或1打开。

    3.Bob不知道Alice如何打开承诺了的但尚未打开的模糊点。即使Alice打开别的模糊点之后，也是如此。

    4.模糊点所带的信息除Alice承诺的比特外，不再有任何信息。模糊点本身，连同Alice承诺和开启模糊点的过程，与Alice希望对Bob保密的别的东西不相关。