多中心的匿名投票协议

在机器统治世界提到，随着科技的发展，我们可以直接用机器来替代政府。所谓机器统治世界，并不意味着机器是世界的主人。机器还是听命于人类，只不过以一种无法被干预的民主投票的方式。所以，机器统计世界的第一要解决的问题就是投票协议。

现在匿名投票已经有很多实现，它们各有缺陷，有的复杂有的简单。这篇文章的方法来自论文Secure Voting Using Partially Compatible Homomorphisms，依靠多中心来实现投票的匿名性。

1. 从一个简单实现说起

如果把投票理解为打分，匿名投票非常类似于如何匿名统计平均收入这个问题：

假设你参加一个大学同学的同学聚会，现在大家对毕业后大家的平均收入水平很感兴趣。但基于各种原因，每个人都不想让别人知道自己的收入水平。能否有一个方法，每个人都不会泄漏自己收入的情况下，大家一块儿算出一起的平均收入呢？

一个简单的实现是：

假设共有 n 个人，每个人可以把自己的收入随机的分成 n 份，并把其中 n-1 份分别告诉其他人。每个人把其他人告知的部分与自己留的一份相加为 m(i)，公开所有的 m(i) 再取平均值即可。

但这个实现其实有个致命的缺陷：对具体的参与者而言，他可以谎报自己的收入，从而扭曲总体结果。如果其它人使用了真实的收入，该参与者可以调整谎报的收入差异，仍得到真实的结果。

在投票协议中，这个缺陷便是投票者可以多投或少投。Secure Voting Using Partially Compatible Homomorphisms利用零知识证明的子协议，解决了这个问题。

2. 简化的投票问题

为了简化，假设投票者只有yes和no两种选项，对应投票值为 1 和-1。目标是在不暴露每个投票者选择的情况下，统计所有有效投票值的和。

为了保持匿名性，假设有两个投票服务器。这两个服务器不会串通。方案可以扩充到多个服务器，使得只要不是所有服务器都串通，仍可保持投票的匿名性。

关键之处在于确保用户的投票的有效性。

3. 双中心的投票协议

3.1. 具体过程

1. 两个投票中心选择素数q，以及两个使用同一个q的 partially compatible homomorphic encryption functions （具体解释见后面） ，假设为(Ec,Cc),c=1,2，其中Ec为公钥，所有人可见，Cc为私钥，仅投票中心可见。
2. 每个投票者i将自己的投票值vi拆分为两个随机数x(1)i,x(2)i，使得x(1)i+x(2)i=vi。
3. 每个投票者i向每个投票中心申请投票有效性验证，验证算法附后。投票中心可以给每个加密投票结果进行验证性通过的签名。
4. 投票者公开加密过的投票结果Ec(x(c)i),c=1,2。
5. 每个投票中心将所有的投票收集起来，计算 tc=∑iCc(Ec(xi))=∑ixi，并公布结果。两个投票中心公布的结果的和便是最终的投票结果，大于 0 表示yes的投票者更多。

在这个协议里，投票中心的权利是非常受限的。比如最后一步的计票步骤。由于之前选择的密码体系支持Ec(x+y)=Ec(x)Ec(y)，投票中心的计票将是可验证的。大家只需要验证 Ec(tc)=∏iEc(x(c)i) 即可。

投票中心的唯一漏洞是拒绝验票。但这可以通过在第 2 步时，投票结果验证时不附带投票者信息，这样投票中心无法进行选择性拒绝验票。

3.2. 投票中心的秘钥选择

投票中心需要选择一种特殊的加密体系，作者称之为「partially compatible homomorphic encryption functions」。它满足week homomorphic条件，即E(x+y)=E(x)×E(y)。

一个可行的选择是Benaloh Crypto System。

3.3. 投票者投票有效性验证

协议中关键步骤是投票者的有效性验证。上面步骤里提到让投票中心进行验证。事实上，该验证协议可以由任何人执行，也就是说我们可以设置独立的验证中心。

假设投票者公开的两个加密投票为E(x(1))和E(x(2))，验证中心需在无法获知真实值得情况下，确认x(1)+x(2)∈{1,−1}。

验证步骤：

1、投票者随机选取 r∈Zq 和 s∈1,−1，并计算R=H(r)（H为大家公认的一个 HASH 方式，比如SHA256），以及计算下面两个值：

然后投票者需公开(Y1,Y2,R)。

2a、验证者以12的概率要求投票者公布r和s。验证中心可以验证H(r)=R和Y1，Y2的结果无误。

2b、验证者以12的概率要求投票者公布s(x(1)+r)和s(x(2)−r)，这样可以通过验证Y1和Y2，并且计算s(x(1)+x(2))=s(x(1)+r)+s(x(2)−r)确认x1+x2∈{1,−1}。

若投票者的投票不合法，那么每次验证，都会有12的概率被发现。如果进行足够多次，可以将非法投票的概率降到 0。并且这些验证可以同时进行。

而在验证过程中，只要验证者未能同时获取E1和E2的解密秘钥，投票者的选择仍是秘密。

4. 方案缺陷

这里最大的缺陷是中心化的，虽然通过双中心的方式降低了风险。但在合谋时，用户的选票还是会被泄露。多中心可以降低泄露的风险（必须所有中心都合谋才会泄露隐私），但方案也要复杂得多。而且一旦某个中心突然拒绝合作，便会造成选举失败。

另外还有一个更大的缺陷（不确定我是否搞错了），投票中心的秘钥是同一个体系的，这意味着需要有一个更大的协议（或者说权利中心），来协调这两个密码体系。这个权利中心可能会掌握整个密码体系，从而成为该投票协议最大的弱点。

Q. E. D.