多中心的匿名投票协议

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

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

在这个协议里，投票中心的权利是非常受限的。比如最后一步的计票步骤。由于之前选择的密码体系支持\(Ec(x+y) = Ec(x)Ec(y)\)，投票中心的计票将是可验证的。大家只需要验证 \( Ec(tc) = \prodi Ec(xi^{(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），以及计算下面两个值：

$$ \begin{eqnarray} Y1=E1(s(x^{(1)} + r)) &=& (E(x^{(1)})E(r))^s \\ Y2=E2(s(x^{(2)} - r)) &=& (E(x^{(2)})E(r)^{-1}))^s \end{eqnarray} $$

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

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

2b、验证者以\(\frac12\)的概率要求投票者公布\(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\in\{1, -1\}\)。

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

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

4. 方案缺陷

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

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

作者暂无likerid, 赞赏暂由本网站代持，当作者有likerid后会全部转账给作者（我们会尽力而为）。


Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: