多中心的匿名投票协议

作者: , 共 2764 字
系列:机器统治世界

查看该系列所有文章

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

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

1. 从一个简单实现说起

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

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

一个简单的实现是:

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

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

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

2. 简化的投票问题

为了简化,假设投票者只有yesno两种选项,对应投票值为 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),以及计算下面两个值:

$$ \begin{eqnarray} Y_1=E_1(s(x^{(1)} + r)) &=& (E(x^{(1)})E(r))^s \\ Y_2=E_2(s(x^{(2)} - r)) &=& (E(x^{(2)})E(r)^{-1}))^s \end{eqnarray} $$

然后投票者需公开\((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.

系列: 机器统治世界 »
最近《流浪地球》的热映,掀起了科幻热潮。很多人都在为电影和小说里的情节和逻辑争论不休。而我更感兴趣的是政府形态。
今天北京车牌摇号开奖,如果只有一倍概率,中签概率只有万分之四,估计这一辈子都中不了吧。北京车牌目前有巨大的利益,组织者如何保证其中没有猫腻呢?
类似文章:
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》
相似度: 0.102
最近《流浪地球》的热映,掀起了科幻热潮。很多人都在为电影和小说里的情节和逻辑争论不休。而我更感兴趣的是政府形态。
今天北京车牌摇号开奖,如果只有一倍概率,中签概率只有万分之四,估计这一辈子都中不了吧。北京车牌目前有巨大的利益,组织者如何保证其中没有猫腻呢?
比特币协议里使用了 ECDSA (椭圆曲线签名算法),我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科,才发现它们之间的差异挺大。
IT » 比特币
最近 bitcoin 很火,我也是最先从云风那里了解到的,后来发现李笑来&霍炬对其都有涉及。不过他们对其具体技术原理的描述还是不够细致,所以我自己把bitcoin wiki又重新看了一遍。 看完之后,疑惑挺多,我对这个体系远没有前面三位这么乐观。诚然,它会成为"Geeks "手中的玩物甚至灰色交易的工具,但要说的达到「一出天下反」的程度,那还需要解决一些技术和金融方面的问题。
本科同学木瑶的窗子最近写了两篇文章,分别关于机器证明和投票,是这两个话题写的最好的介绍性文章了,分享给大家看一看:
IT » 比特币
上篇大致描述了 bitcoin 的技术原理,只想说明一件事情: bitcoin 的协议是可靠的,它保证了 bitcoin 虚拟货币的信用问题,别人不会偷走我的 bitcoin ,我拿到的 bitcoin 也是真实可靠的。使用 bitcoin 交易有很多好处,可以轻易列出一大堆:
IT » 比特币
今年 6 月份,我在bitcoin 的技术和金融缺陷一文中提出了Bitcoin的一些技术上和金融上的缺陷,其中一条是认为 Bitcoin 并不完全是匿名的:
最近《流浪地球》的热映,掀起了科幻热潮。很多人都在为电影和小说里的情节和逻辑争论不休。而我更感兴趣的是政府形态。
最近在知乎上看到一篇回答,提到中国的人才踩踏效应。我以前也有类似看法。其实不光人力资源上,在商业模式上也是如此,共享单车就是一个典型的例子。作者写得很清楚,复制过来保留一份备份。