无需投票中心的安全协议

FOO协议需要管理机构和计票机构，这里我们将介绍一个无须这两个机构的协议。在这个协议中，投票者互相监督，但由于操作困难，一般只适用于少数几个人的投票。

假设Alice、Bob、Carol和Dave正在对一个特殊问题进行是或否（0或1）的投票。假设每个投票者都有一个公开密钥和一个私钥，且每个人都知道其他人的公开密钥。

（1）每个投票者选择一张选票并做以下事情。

①在他们的选票上附一个随机字符串。

②用Dave的公开密钥加密步骤①的结果。

③用Carol的公开密钥加密步骤②的结果。

④用Bob的公开密钥加密步骤③的结果。

⑤用Alice的公开密钥加密步骤④的结果。

⑥在步骤⑤的结果中附上一个新的随机字符串，并用Dave的公开密钥对它加密。他们记下这个随机字符串的值。

⑦在步骤⑥的结果中附上一个新的随机字符串，并用Carol的公开密钥对它加密。他们记下这个随机字符串的值。

⑧在步骤⑦的结果中附上一个新的随机字符串，并用Bob的公开密钥对它加密。他们记下这个随机字符串的值。

⑨在步骤⑧的结果中附上一个新的随机字符串，并用Alice的公开密钥对它加密。他们记下这个随机字符串的值。

如果E是加密函数，R是一个随机字符串，且V是选票，则选票看起来像：EA（R5，EB（R4，EC（R3，ED（R2，EA（EB（EC（ED（V，R1））））））））。

所有的投票者记下计算中每一点的中间结果。在协议中后面将会用这些结果来确定他们的选票是否被计数。

（2）每个投票者把他的选票送给Alice。

（3）Alice用她的私钥对所有的选票解密，接着将那一级中所有随机字符串删去。

（4）Alice置乱所有选票的秩序并把结果送给Bob。每张选票现在看起来像这个样子：EB（R4，EC（R3，ED（R2，EA（EB（EC（ED（V，R1）））））））。

（5）Bob用他的私钥对所有的选票解密，查看他的选票是否在选票集中，删去那一级中所有随机字符串，置乱所有的选票然后把结果送给Carol。每张选票现在看起来像这个样子：(https://www.daowen.com)

EC(R3,ED(R2,EA(EB(EC(ED(V,R1))))))。

（6）Carol用她的私钥对所有的选票解密，查看她的选票是否在选票集中，删去那一级所有的随机字符串，置乱所有的选票，然后把结果送给Dave。每张选票现在看起来像这个样子：ED（R2，EA（EB（EC（ED（V，R1）））））。

（7）Dave用他的私钥对所有的选票解密，查看他的选票是否在选票集中，删去那一级中所有随机字符串，置乱所有的选票，并把结果送给Alice。每张选票现在看起来像这个样子：EA（EB（EC（ED（V，R1））））。

（8）Alice用她的私钥对所有选票解密，查看她的选票是否在选票集中，签名所有选票，并把结果送给Bob、Carol和Dave。每张选票现在看起来像这个样子：SA（EB（EC（ED（V，R1））））。

（9）Bob验证并删去Alice的签名。他用他的私钥对所有的选票解密，查看他的选票是否在选票集中，对所有的选票签名，然后把结果送给Alice、Bob和Dave。每张选票现在看起来是这个样子：SB（EC（ED（V，R1）））。

（10）Carol验证并删去Bob的签名。她用她的私钥对所有选票解密，查看她的选票是否在选票集中，对所有的选票签名，然后把结果送给Alice、Bob和Dave。每张选票现在看起来是这个样子：SC（ED（V，R1））。

（11）Dave验证并删去Carol的签名。他用他的私钥对所有选票解密，查看他的选票是否在选票集中，对所有的选票签名，然后把结果送给Alice、Bob和Carol。每张选票现在看起来是这个样子：SD（V，R1）。

（12）所有人验证并删去Dave的签名。通过检验以确信他们的选票在选票集中（通过在选票中寻找他们的随机字符串）。

（13）每个人都从自己的选票中删去随机字符串并记录每张选票。

在这个协议中，如果有人试图进行欺骗，Alice、Bob、Carol和Dave将立即知道。下面我们来尝试进行欺骗。

如果人有想把假票塞进票箱，在第（3）步当Alice收到比人数多的选票时就会发现这一企图。如果Alice试图把假票塞进票箱，Bob将在第（4）步中发现。

还有一种欺骗方法是用一张选票替换另一张。因为选票是用各种不同的公开密钥加密的，任何人都能按其需要创造很多有效的选票。这里解密协议有两轮：第一轮包括第（3）步至第（7）步，第二轮包括第（8）步至第（11）步。替换选票会在不同轮次被分别发现。

如果有人在第二轮中用一张选票替换另一张，他的行为会立即被发现。在每一步上选票被签名并送给所有投票者。如果一个（或更多）的投票者注意到他的选票不在选票集中，他就立即中止协议。因为选票在每一步都签了名，而且每个人都能反向进行协议的第二轮，所以很容易发现谁替换了选票。

在协议的第一轮用一张选票替换另一张显得更为高明。Alice不能在第（3）步中这样做，因为Bob、Carol或Dave会在第（5）、（6）、（7）步中发现。Bob可以第（5）步中这样做。如果他替换了Carol或Dave的选票（这里，他不知道哪张选票对应哪个投票者），Carol或Dave将在第（6）步或第（7）步中发现，他们不知道谁篡改了他们的选票（虽然这一定是某个已经处理过选票的人），但他们知道他们的选票被篡改了。如果Bob幸运地挑选了Alice的选票来替换，她要到第二轮才会发现。接着，Alice在第（8）步中会发现她的选票遗失了。但她仍然不知道谁篡改了她的选票。在第一轮中，选票在从一步到另一步时被搅乱并且未被签名；任何人都不可能反向跟踪协议以确定谁篡改了选票。

另一种形式的骗术是试图弄清楚谁投了谁的票。因为置乱是在第一轮，所以任何人都不可能反向跟踪协议，并把投票者与选票联系起来。在第二轮中删去随机字符串对保护匿名性来说关系重大。如果它们未被删除，通过用置乱者的公开密钥对出现的选票重新加密便能将选票的置乱还原。由于协议的固有性质，选票的机密性是有保障的。

其实，即使一样的选票在协议的每一步都被加密成不同的选票，因为有初始随机字符串R1，也只有到第（11）步人们才能知道选票的结果。

但是，这个协议也存在一些问题。首先，这个协议计算量特别大，它在实际的选举中无法奏效，因为有成千上万的投票者。其次，Dave先于其他人知道选举结果。虽然他还不能影响选举结果，但这给了他一些别人没有的权力。另一方面，带有投票中心的投票方案是合乎实际情况的。最后，Alice能拷贝其他人的选票，即使事先她并不知道它是什么。设想一个Alice、Bob和Eve的三人选举。Eve并不关心选举结果，但是她想知道Alice是怎样投票的。因此她可以拷贝Alice的选票，从而保证选举的结果等于Alice的投票。