【文章】第六章：深奥的协议 - 6.1 保密选举

第六章 深奥的协议

6.1 保密选举

    除非有一个协议既能防止欺骗又能保护个人隐私，否则计算机化的投票永远不会在一般选举中使用。理想的协议至少要有这样六项要求：

    （1）只有经授权的投票者才能投票。

    （2）每个人投票不得超过一次。

    （3）任何人都不能确定别人投谁的票。

    （4）没有人能复制其它人的选票。（这一点证明是最困难的要求。）

    （5）没有人能修改其他人的选票而不被发现。

    （6）每个投票者都可以保证他的选票在最后的表中被计算在内。

    此外，有些投票方案可能有如下要求：

    （7）每个人都知道谁投了票及谁没有投。

    在讨论具有这些特性的复杂投票协议前，我们先看几个比较简单的协议。

简单投票协议^#1

    （1）每个投票者利用中央制表机构（CTF）的公钥加密他们的选票。

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

    （3）CTF将选票解密，制表，公布结果。

    这个协议问题成堆。CTF不知道选票从何而来，故它甚至不知道选票是否来自合格的投票者。他们也不知道这些合格的投票者是否投了一次以上的票。在正的一方，没有人能改变其他人的选票，但是当你可以相当容易地将你的选择结果投无数次时，也就没有人试图去修改其他人的选票。

简单投票协议^#2

    （1）每个投票者用他的私钥在选票上签名。

    （2）每个投票者用CTF的公开密钥加密他们的签了名的选票。

    （3）每个投票者把他的选票送给CTF。

    （4）CTF解密这些选票，检查签名，将选票制表并公布结果。

    这个协议满足了性质1和性质2：只有被授权的投票者才能投票，并且任何人都不能投一次以上的票。CTF在第（3）步中记录收到的选票。每张选票都用投票者的私钥签名，故CTF知道谁投了票？谁没有投票？以及每个投票者投了多少次？如果出现没有由合格投票者签名的选票，或者出现另一张由一个已投过票的投票者签名的选票，那么机构可以不计这张选票。没人能改变其他任何人的选票，即使他们在第（2）步截获了它。这个协议的问题在于签名附在选票上，故CTF知道谁投了谁的票。用CTF的公开密钥加密选票阻止了任何人在协议进行中窃收，并了解谁投了谁的票，但是你得完全信任CTF。它类似于有一个选举监督员在背后盯着你把票投入票箱。

    这两个例子说明要满足安全投票协议的前三个要求是多么困难，更别说其它的要求了。

使用盲签名投票

    我们需要以某种办法切断投票者与选票的关系，同时仍能保持鉴别。盲签名协议正好可以做到这一点。

    （1）每个投票者产生10个消息集，其中对每一种可能结果都有一张有效选票（例如，如果选票是一个“Yes”或“No question”，则每个集合中包含两张选票，一张“Yes”且另一张“No”）。每条消息也包含一个随机产生的识别号，这个数要大到足以避免和别的投票者重复。

    （2）每个投票者分别隐蔽所有的消息（见5.3节）并把它们同盲因子一道送给CTF。

    （3）CTF检查它的数据库以保证投票者先前不曾以他们的签名提交过隐蔽好的选票。它打开9个集合以检查它们是否正确形成，然后它分别签名这个集合中的每一条消息。接着把它们送还给投票者，并把投票者的名字存在它的数据库中。

    （4）投票者除去这些消息的隐蔽，留下由CTF签名的一组选票（这些选票签了名，但未加密，故投票者能轻易地知道哪 张选票是“Yes”及哪张是“No”）。

    （5）投票者选择其中一张选票，（哈，很民主）并用CTF的公开密钥对它加密。

    （6）投票者投出他们的选票。

    （7）CTF将选票解密，检查签名，检查它的数据库是否有重复的识别号，保存这个序号并将选票制表。公布选举结果以及每个序号和其相关的选票。

    一个恶意的投票者，我们不妨称之为Mallory，他不可能欺骗这个系统。盲签名协议确保他的选票是独一无二的。如果他试图在同一次选举中投两次票，则CTF将会在第（7）步中发现重复的系列号并把第二张选票扔掉。如果他试图在第（2）步中得到多张签了名的选票，则CTF将在第（3）步中发现这一点。因为Mallory不知道这个机构的私钥，故他也不能产生他自己的选票。同样他也不能截取和改变其他人的选票。

    第（3）步的分割——选择协议是为了保证选票的唯一性。没有这一步，Mallory可以制造出大量的相同的选票，除了识别号不同，并且使这些选票全都有效。

    一个恶意的CTF不可能了解个人如何投票。因为盲签名协议防止了这个机构在人们投票前看到选票上的序码，则CTF无法把它签名的隐蔽好的选票与最终投出的选票联系起来。公布系列号清单和它们的相关选票使得投票者能肯定他们的选票被正确地统计制表。

    这里仍然有问题。如果第（6）步不是匿名的，CTF能记录下谁投了哪 张选票，那么它就能知道谁投谁的票。但是，如果它收到的选票在一个锁着的选票箱里，并且随后把它们制表，则它就不能记录。两样，还有，虽然CTF不能把选票同个人联系起来，但它能产生大量签名的有效选票，供他自己进行欺骗。而且如果Alice发现CTF修改了她的选票，她没有办法证明。[1195，1370]中有一个类似的协议试图弥补这些问题。

带两个中央机构的投票

    一种解决办法是将CTF一分为二。没有哪一方自己有能力进行欺骗。

    下面这个协议使用一个中央合法机构（CLA）来证明投票者，以及一个单独的CTF来计票[1373]。

    （1）每个投票者发送一条消息给CLA要求得到一个有效数字。

    （2）CLA送还给投票者一个随机的有效数字。CLA保持一张有效数字的列表，CLA也保留一张有效数字接受者的名单，以防有人试图再次投票。

    （3）CLA把有效数字的列表送给CTF。

    （4）每个投票者选择一个随机识别号。他们用该识别号、从CLA收到的有效数字和他们的选票一起产生一条消息，把这消息送给CTF。

    （5）CTF对照它在第（3）步中从CLA收到的列表来检验有效数字。如果数字存在，CTF就把它划掉（防止任何人投票两次）。CTF把识别号加到投了某位候选者的人员名单上，并在记数中加一。

    （6）在收到了所有的选票后，CTF公布结果、识别号以及这些识别号所有者投了谁的票。

    就象前面的协议一样，每个投票者能够看到识别号的列表，并在其中找到他自己的识别号，这就证明他的选票被计了数。当然，协议中各方之间传递的所有消息应当加密并签名，以防止一些人假冒另一些人或截取传送。

    因为每个投票者都要寻找他们的识别字符串，故CTF不能修改选票。如果投票者找不到他的识别号，或者发现他的识别号在不是他们所投票的记录中，他会立即知道这中间有舞弊行为。因为CTF受CLA监督。所以它不能把假选票塞进投票箱。CLA知道有多少个投票者正被证明及他们的鉴别数字，并会检测到任何窜改。

    Mallory不是一个合格的投票者，他可以试图通过猜测有效数字来进行欺骗。但通过使可能的有效数字比实际有效数字大得多的方法可使这种威胁降到最低限度。例如，一百万个投票者的一百位数字。当然，有效数字必须是随机产生的。

    尽管这样，CLA在一些方面仍是一个可信任的机构。它能验证出不合格的投票者。它能对合格投票者多次验证。通过让CLA公布被验证的投票者（但不是他们的鉴别数字）的清单可使这种风险最小化。如果这个清单上投票者的数目小于已造表的选票的数目，那么肯定其中有诈。如果被验证的投票者比已造表的选票多，可能意谓着一些被验证的人未投票。很多人注册投票，但却没有将选票投进票箱。

    这个协议也易受CLA和CTF的合谋攻击。如果它们两个串通一气，那它们可以将数据库联系起来并知道谁投了谁的票。

带一个中央机构的投票

    使用一个更复杂的协议能克服CLA和CTF合谋的危险[1373]。这个协议和前面一个基本相同，但作了两处修改：

    ·CLA和CTF是一个组织，并且

    ·ANDOS（见4.13节）用来在第（2）步中匿名分配有效数字。

    因为匿名的密钥分配协议防止了CTF知道哪个投票者得到了哪个有效数字，故CTF没有办法把收到的选票和有效数字联系起来。虽然仍必须相信CTF不会把有效数字给不合格的投票者。即使如此你也可以使用盲签名来解决这个问题。

改进的带单个中央机构的投票

    这个协议也使用ANDOS[1175]。它满足一个好的投票协议的所有六个要求。它不满足第7个要求；但有另外两个性质，我们将其列在这一节的开始：

    （7）投票者在一个给定的时间内改变主意。（即，收回他们的选票并重新投票。）

    （8）如果投票者发现他们的选票被误计，他们能够鉴别并纠正这个问题，同时不会危害到他投票的秘密。

    下面是这个协议：

        （1）CTF公布所有合法投票者的名单。

        （2）在一个指定的截止日期内，每一投票的人都把他的投票意图告诉CTF。

        （3）CTF公布参加选举的投票者。

        （4）每个投票者都使用ANDOS协议，收到一个鉴别数字I。

        （5）每个投票者产生一个公钥/私钥密钥对：k和d。如果v是选票，他们产生出下列消息并将它送给CTF：

I, E_k（I，v）

        该消息必须匿名发送。

        （6）CTF通过公布E_k（I，v）确认收到选票。

        （7）每个投票者送给CTF：

I，d

        （8）CTF用d解密选票。在选举结束时，它公布选举结果和对每张不同选票公布所有包含那张选票的所有E_k（I，v）值的列表。

        （9）如果投票者发现他们的选票没有被正确计数，他们通过给CTF发送：

I, E_k（I，v）, d

        来表示抗议。

        （10）如果投票者想把他的选票从v改到vˊ（这在一些选举中是可能的），他们送给CTF：

I, E_k（I，v）vˊ

    有一种不同的投票协议用盲签名代替ANDOS，但其本质是相同的[585]。步骤（1）至步骤（3）是实际投票的开端。它们的目的是弄清楚并公布实际投票者的总数。虽然一些人可能不参加，但它减少了CTF增加假冒选票的可能性。

    在第（4）步中，两个投票者得到相同的鉴别数字是可能的。通过让可能的鉴别数字远远超过实际的投票者的数目能使这种可能性最小化。如果两个投票者提交了带相同鉴别标记的选票，CTF就产生一个新的鉴别数字Iˊ，选择两张选票中的一张并公布：

IˊE_k（I，v）

    这张选票的所有者认出它来，并通过重复第（5）步，交上第二张带新的鉴别数字的选票。

    第（6）步让所有投票者能够查知CTF确实收到了他们的选择。并且如果他们的投票被误计了，他们可以在第（9）步中证明这一情况，假设在第（6）步中投票者的选票是对的，则在第（9）步中他们发送的消息构成了他们选票被误计的证据。

    这个协议的一个问题是一个腐败的CTF可给在第（2）步中响应的人分发选票，但不能给实际不投票的人分发选票。另一个问题是ANDOS协议的复杂性。作者建议把一大群投票人分成几个小群，如同一个个选区。

    另一个更为严重的问题是CTF可能漏计选票。这个问题无法解决：Alice宣称CTF故意漏计她的选票，但是CTF宣称投票人没有投票。

不带中央制表机构的投票

    这个协议完全省却了使用CTF，投票者互相监督。它是由Michael Merrit设计的[452，1076，453]。它是如此难操作以至只有在少数几个人中才能实际地实现，然而我们可以从中学到一些东西。

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

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

    （a）在他们的选标上附一个随机字符串。

    （b）用Dave的公开密钥加密步骤（a）的结果。

    （c）用Carol的公开密钥加密步骤（b）的结果。

    （d）用Bob的公开密钥加密步骤（c）的结果。

    （e）用Alice的公开密钥加密步骤（d）的结果。

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

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

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

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

    如果E是加密函数，R是一个随机字符串，且V是选票，则选票看起来像：

E_A（R₅，E_B（R₄，E_C（R₃，E_D（R₂，E_A（E_B（E_C（E_D（V，R₁））））））））

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

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

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

    （4）Alice置乱所有选票的秩序并把结果送给Bob。每张选票现在看起来像这个样子：

E_B（R₄，E_C（R₃，E_D（R₂，E_A（E_B（E_B（E_C（E_D（V，R₁）））））））

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

E_C（R₃，E_D（R₂，E_A（E_B（E_C（E_D（V，R₁））））））

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

E_D（R₂，E_A（E_B（E_C（E_D（V，R₁）））））

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

E_A（E_B（E_C（E_D（V，R₁））））

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

S_A（E_B（E_C（E_D（V，R₁）））））

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

S_B（E_C（E_D（V，R₁）））

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

S_C（E_D（V，R₁））

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

S_D（V，R₁）

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

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

    这个协议不仅起作用，而且还能自我判决的。如果有人试图进行欺骗，Alice、Bob、Carol和Dave将立即知道。这里不需要CTF和CLA。为了弄清楚这是怎样起作用的，让我们来试演行骗。

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

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

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

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

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

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

    这个协议的问题是什么呢？首先，这个协议计算量特别大。前面所述的例子仅有四个投票者，就已经很复杂了。这个协议在实际的选举无法凑效，因为有成千上万的投票者。其次，Dave先于其他人知道选举结果。虽然他还不能影响选举结果，但这给了他一些别人没有的权力。另一方面，带有中央化的投票方案也是合乎实际情况的。

    第三个问题是Alice能拷贝其他人的选票，即使事先她并不知道它是什么。为了弄清这是一个问题的原因，设想一个Alice，Bob，和Eve的三人选举。Eve并不关心选举结果，但是她想知道Alice是怎样投票的。因此她拷贝Alice的选票，保证选举的结果等于Alice的投票。

其他投票方案

    人们已经提出许多复杂的安全选举协议。它们来自两个不同风格的基本协议。有一些混合协议，象“没有中央制表机构的协议”，这里每人的选票都被混合以便没有人能把选票与投票者联系起来。

    也有被分开的协议，单独的选票在不同的制表机构被分散开，单独的一个机构不能欺骗投票者[360，359，118，115]。这个协议仅在政府的（或管理投票的机构的）“不同”部门不串通起来对付投票者的情况下才能保护投票者的隐私。（将一个中央机关分成不同部门，仅在它们都聚在一起时才可信任的想法来自文献[316]）。

    文献[1371]中有一个被分开的协议。它的基本思想是每一个投票者把他的投票分成几分。例如，如果选票是“yes”或“no”，可以用1代表“yes”而0代表“no”；然后投票者产生几个数字，它们的和为1或0。每一分送给制表机构，一个部分一份，并且每一分都被加密邮寄。每个中心标记它收到的那些部分（有一个验证标记是否正确的协议），最终的投票结果是所有的标记之和。还有一个协议保证每个投票者的部分数值和为1或0。

    David Chaum提出的另一个协议[322]，它确保跟踪任何企图破坏选举的投票人。但是，那样做必须重复选举过程，并在不得干扰投票者的情况下；这种方法对于大规模选举是不实用的。

    另一个更复杂的投票协议解决了一些这方面问题[770，771]。甚至有一个投票协议使用了多密钥密码[219]。还有一个投票协议，宣称对大规模选举是实用的，见文献[585]。文献[347]允许投票者弃权。

    投票协议有效、但他们使买卖选票变得更加容易。这种动机变得相当强烈，因为买方相信出售的选票是合法的。一些协议被设计成不要收条的，这使得投票者以某种方式向其他人证明他的投票变得不可能[117，1170，1372]。

文章来源于lcx.cc:【文章】第六章：深奥的协议 - 6.1 保密选举

相关推荐: 【视频】国家地理：《奇妙的人体机器》

国家地理：奇妙的人体机器     人体是我们最熟悉却也最神秘的：动作令人惊叹，构造十分奇妙，官能异常敏锐，并具备超强的理解能力。从清晨到午夜，人体机器都在不停运转。让我们展开奇妙的旅程，深入了解人体每天展现的奇迹。     有一部机器，一年365天，一天24小…