多中心的匿名投票协议

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

现在匿名投票已经有很多实现，它们各有缺陷，有的复杂有的简单。这篇文章的方法来自论文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 （具体解释见后面） ，假设为$(E_c,C_c), c=1,2$，其中$E_c$为公钥，所有人可见，$C_c$为私钥，仅投票中心可见。
2. 每个投票者$i$将自己的投票值$v_i$拆分为两个随机数$x_i^{(1)}, x_i^{(2)}$，使得$x_i^{(1)} + x_i^{(2)} = v_i$。
3. 每个投票者$i$向每个投票中心申请投票有效性验证，验证算法附后。投票中心可以给每个加密投票结果进行验证性通过的签名。
4. 投票者公开加密过的投票结果$E_c(x_i^{(c)}), c=1,2$。
5. 每个投票中心将所有的投票收集起来，计算 $t_c= \sum_i C_c(E_c(x_i)) = \sum_i x_i$，并公布结果。两个投票中心公布的结果的和便是最终的投票结果，大于 0 表示yes的投票者更多。

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

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

3.2、投票中心的秘钥选择

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

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

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

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

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

验证步骤：

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

然后投票者需公开$(Y_1, Y_2, R)$。

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

2b、验证者以$\frac12$的概率要求投票者公布$s(x^{(1)}+r)$和$s(x^{(2)}-r)$，这样可以通过验证$Y_1$和$Y_2$，并且计算$s(x^{(1)}+x^{(2)})=s(x^{(1)}+r)+s(x^{(2)}-r)$确认$x_1+x_2\in\{1, -1\}$。

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

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

4、方案缺陷

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

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

Q. E. D.