电子投票是基于密码学技术设计并通过网络实现的一种投票方式. 与传统的唱票表决相比, 电子投票的投票和计票过程更高效、选举结果更准确. 随着互联网与密码学技术的发展, 电子投票得到大力发展. 近年来, 电子投票系统在许多西方国家的选举中得到应用, 其中爱沙尼亚首先在国家层面的选举使用电子投票. 目前, 美国、加拿大等地的议会和立法中已开始使用电子投票. 我国部分领域也在尝试使用电子投票, 其中2005年上海市长宁区某街道进行团支部直选时首次在政治领域使用电子投票.

最早的电子投票方案可追溯到1981年, 由 Chaum^[1]基于混合网络和RSA公钥加密体制提出. 1992年, Fujilka等人^[2]基于盲签名提出了可适用于大规模选举的FOO方案, 使电子投票走向实用. 1997年, Cramer等人^[3]首次提出了多候选人的电子投票问题, 并利用ElGamal加密系统设计了一个多选一的电子选举方案, 该方案需要可信的计票中心参与接收并统计选票. 2001年, Damgård等人^[4]基于Paillier加密系统提出了一个多选多的电子投票方案, 该方案无法避免重复投票现象且需要可信计票机构参与. 2006年, 仲红等人^[5]基于安全多方求和提出一个无需第三方计票机构参与的多选多电子投票方案, 但选举结束后会公开所有候选人的得票数. 2012年, Pang等人^[6]基于混合网络和PET协议提出一个多选多电子选举方案. 2015年, 杨婷婷等人^[7]基于安全多方排序协议设计了一个多选多电子投票方案, 但方案使用的排序协议要求参与者两两之间有安全信道, 对通信环境要求较高. 2018年, 娄宇等人^[8]基于全同态加密算法提出一个多候选人的电子投票方案, 其计票工作由第三方计票中心完成且公开所有候选人得票数. 2019年, 刘霆等人^[9]将随机线性分组码的秘密分享应用于多候选人电子投票方案中, 解决了防投票记录篡改、关键信息存储的安全性等问题. 同年, 付伟伟等人^[10]基于随机矩阵提出一个多选一电子投票方案, 该方案满足可验证性, 但需要计票中心参与. 2021年, 邵清等人^[11]基于ElGamal强盲签名和区块链技术提出了电子投票方案, 此方案没有明确选举场景、选票形式等, 重点关注选票的可验证性、不可篡改性等问题, 且用智能合约取代可信第三方完成计票. 文献[12-16]等结合区块链、同态加密等技术提出了完整的安全电子投票系统.

保密选票内容是安全电子投票方案的一个基本要求. 但在计票阶段, 候选者得票数同样属于关键信息. 因为破坏者可能根据候选人之间得票数的差异, 在下次选举时通过拉拢选票的手段, 破坏选举的公平性. 因此, 文献[6]首次提出了投票方案中“全隐私”的概念, 是指既保护选民选票内容又保护候选人得票数. 上述文献[6,7]提出的方案保护了落选者得票数.

为保密选票内容, 可以用加密技术对选票信息进行加密. 同时为方便后续计票, 加密后的信息需要满足一定的同态性质. 而同态加密^[17]满足上述需求, 能够在不解密密文的前提下, 通过对密文的操作实现对相应明文的计算. 姚期智^[18]提出的安全多方计算主要解决互不信任的数据拥有者之间的安全协同计算问题, 基于此思想设计电子投票方案可解决计票时第三方机构参与的问题.

尽我们所知, 已有的电子投票方案仅统计候选人的赞成票数. 然而在实际的选举场景中, 时常会遇到以下情况: 某些候选人赞成票数名列前茅, 但选民对其反对声音也很高. 例如, 在有50位合法选民的选举活动中, 有两位候选人得票情况如表1. 根据已有的电子投票方案候选人2获胜, 但是候选人1当选更能反映选民的意愿.

为了避免上述有争议的选举结果出现, 本文在综合考虑候选人赞成票数和反对票数的前提下, 基于安全多方计算, 结合ElGamal同态加密系统提出一个无需第三方计票机构参与、全隐私的多选多电子投票方案.

1 预备知识 1.1 半诚实模型及其安全性定义

本文在半诚实模型下考虑方案的安全性. 半诚实参与者是指参与者会忠实执行协议, 但他们会利用收到的中间信息试图推断其他参与者的输入.

设n个参与者 $ {P_i}\;\left( {i = 1, 2, \cdots , n} \right) $ 分别持有私密信息 $ {X_i} $ , 记 $ X = \left\{ {{X_1}, {X_2}, \cdots , {X_n}} \right\} $ . 他们利用协议 $ \pi $ 合作计算函数 $ f\left( X \right) = \left( {{f_1}\left( X \right), \cdots , {f_n}\left( X \right)} \right) $ , 计算结束后 $ {P_i} $ 收到 $ {f_i}(X) $ . 协议 $ \pi $ 执行过程中, 记 $ {P_i}\left( {i = 1, 2, \cdots , n} \right) $ 的视图为 $ VIEW_i^\pi \left( X \right) $ . 对于部分参与者 $ \tau {\text{ = }}\left( {{P_{{i_1}}}, {P_{{i_2}}}, \cdots , {P_{{i_s}}}} \right) $ $ \subset \left( {{P_1}, {P_2}, \cdots , {P_n}} \right) $ , 记:

$ VIEW_\tau ^\pi \left( X \right) = \left( {\tau , VIEW_{{i_1}}^\pi \left( X \right), \cdots , VIEW_{{i_s}}^\pi \left( X \right)} \right) $

(1)

定义1 (半诚实模型下协议的安全性^[19]). 当参与者都是半诚实参与者时, 若存在概率多项式时间算法S, 使得对于任意的 $ \tau $ , 都有式(2)成立,

$ \left\{ {S\left( {\tau , {X_{{i_1}}}, {X_{{i_2}}}, \cdots , {X_{{i_s}}}, {f_\tau }\left( X \right)} \right)} \right\}\mathop \equiv \limits^c \left\{ {VIEW_\tau ^\pi \left( X \right)} \right\} $

(2)

则称协议 $ \pi $ 保密地计算了函数 $ f(X) $ , 其中符号 $\mathop \equiv \limits^c $ 表示计算上不可区分.

1.2 ElGamal加密系统

ElGamal加密系统^[20]是一种具有乘法同态性的公钥加密系统, 本文将使用文献[21]中构造的具有加法同态性的门限ElGamal加密系统, 描述如下:

(1)密钥生成算法

对给定安全参数k, 系统生成一个k比特的大素数p和循环群 $ Z_p^* $ 的一个生成元g. 每个 $ {P_i} $ $( i = 1, 2, \cdots , n )$ 选取随机数 $ {x_i} $ 作为其持有的私钥份额, 公布 $ {h_i} = {g^{{x_i}}} \boldsymbolod p $ , 则公钥为 $h = \displaystyle\prod\nolimits_{i = 1}^n {{h_i}} = {g^{\sum\nolimits_{i = 1}^n {{x_i}} }}\boldsymbolod p$ .

(2)加密算法E

对于消息 $ M\left( {M \in Z_p^*} \right) $ , 选取随机数r, 密文为: $ E\left( M \right) = $ $ \left( {{c_1}, {c_2}} \right) = \left( {{g^r}\boldsymbolod p, {g^M}{h^r}\boldsymbolod p} \right) $ .

(3)解密算法D

对于密文 $ E\left( M \right) = \left( {{c_1}, {c_2}} \right) $ , $ {P_i}\left( {i = 1, 2, \cdots , n} \right) $ 计算 $ {w_i} = $ $ {c_1}^{{x_i}}\boldsymbolod p $ 并公布, 所有参与者共同解密得:

$ {g^M}{\text{ = }}{c_2} \cdot {\left[ {\prod\nolimits_{i = 1}^n {{w_i}} } \right]^{ - 1}}\boldsymbolod p $

(3)

与ElGamal加密系统类似, 该加密系统具有语义安全性. 需要注意的是此加密系统不具有完全解密性, 解密算法仅可得明文M的幂值 ${g^M}$ .

1.3 IsEq协议

Kissner等人^[22]研究隐私集合运算时提出了IsEq协议. 根据此协议, 对于用同一公钥加密所得的密文 $ {C_1} $ 和 $ {C_2} $ , 若 $ {C_1} $ 和 $ {C_2} $ 是同一明文的密文, 则 $ IsEq\left( {{C_1}, {C_2}} \right){\text{ = 1}} $ ; 否则, $ IsEq\left( {{C_1}, {C_2}} \right){\text{ = 0}} $ .

2 多选多电子投票方案的设计 2.1 投票场景

本文假设有n位选民和m位候选人取得了合法身份标识 $ {P_1}, {P_2}, \cdots , {P_n} $ 和 $ {C_1}, {C_2}, \cdots , {C_m} $ , 有资格进入投票系统参与投票和计票. 选民将从m位候选人中选出k位获胜者. 本方案规定每位获胜者的反对票数均不能超过阈值t. 记所有的获胜候选人构成集合W.

2.2 表决方式

选民 ${P_i}\left( {i = 1, 2, \cdots , n} \right)$ 对候选人 ${C_j}\left( {j = 1, 2, \cdots , m} \right)$ 进行表决得一个三元数组 $\left( {{v_{i, 3j - 2}}, {v_{i, 3j - 1}}, {v_{i, 3j}}} \right)$ , 其3个分量分别对应赞成、反对和弃权3种表决意见. 若选民的表决意见为赞成, 则对应数组为 $\left( {1, 0, 0} \right)$ ; 若选民的表决意见是反对或弃权, 其对应数组为 $\left( {0, 1, 0} \right)$ 或 $\left( {0, 0, 1} \right)$ . ${P_i}\;\left( {i = 1, 2, \cdots , n} \right)$ 对每位候选人依次表决完毕后, 得到数组 ${V_i} = \left( {{v_{i, 1}}, {v_{i, 2}}, \cdots , {v_{i, 3m}}} \right)$ , ${V_i}$ 为 ${P_i}$ 表决后的选票.

2.3 投票方案

本文设计的投票方案分为初始化阶段、投票阶段和计票阶段, 具体过程如下:

2.3.1 初始化阶段

基于门限ElGamal加密系统生成大素数 $p$ 和循环群 $ Z_p^* $ 的生成元 $g$ . 选民 $ {P_1}, {P_2}, \cdots , {P_n} $ 和候选人 $ {C_1}, {C_2}, \cdots , {C_m} $ 分别选取 ${x_i}\left( {i = 1, 2, \cdots , n + m} \right)$ 作为其持有的私钥份额, 计算 ${h_i} = {g^{{x_i}}}\boldsymbolod p$ 并公开. 所有选民和候选人计算公钥 $h={\displaystyle {\prod }_{i=1}^{n\text{+}m}{h}_{i}}\text{=}{g}^{{ {\sum }_{i=1}^{n\text{+}m}{x}_{i}}}\mod\;p$ . 每位候选人 $ {C_j}\;(j = 1, 2, \cdots , $ $ m)$ 选取随机数 ${r_j}$ , 计算密文 ${E_s} = E\left( s \right){\rm{ = }}({g^{{r_j}}}\,\boldsymbolod \,p, $ $ {g^s}{h^{{r_j}}}\,\boldsymbolod \,p)\;\left( {s = 1,2, \cdots ,n} \right)$ , 并保存 ${E_s}$ 以备在计票阶段使用.

2.3.2 投票阶段

选民 ${P_i}\left( {i = 1, 2, \cdots , n} \right)$ 依据第2.2节所述方式表决得选票 ${V_i} = \left( {{v_{i, 1}}, {v_{i, 2}}, \cdots , {v_{i, 3m}}} \right)$ . 接着, ${P_i}\left( {i = 1, 2, \cdots , n} \right)$ 利用门限ElGamal加密系统加密选票 ${V_i}$ 的每个分量得加密选票 ${B_i} = \left( {E\left( {{v_{i, 1}}} \right), E\left( {{v_{i, 2}}} \right), \cdots , E\left( {{v_{i, 3m}}} \right)} \right)$ , 其中 $E\left( {{v_{i, j}}} \right){\text{ = }} $ $ \left( {{g^{{r_{i, j}}}}\boldsymbolod p, {g^{{v_{i, j}}}} \cdot {h^{{r_{i, j}}}}\boldsymbolod p} \right)$ , ${r_{i, j}}$ 为 ${P_i}$ 加密时选取的随机数, 并将加密选票 ${B_i}$ 发送给每位候选人.

2.3.3 计票阶段

计票阶段由所有选民 ${P_i}\;\left( {i = 1, 2, \cdots , n} \right)$ 和候选人 ${C_j}\;\left( {j = 1, 2, \cdots , m} \right)$ 通过交互计算完成, 过程如下.

(1)每个候选人 ${C_j}\;\left( {j = 1, 2, \cdots , m} \right)$ 执行如下计算:

① 将所有加密选票 ${B_i}$ 的第 $3j - 2$ 列和 $3j - 1$ 列中元素求积得:

$ {w_j} = \prod\nolimits_{i = 1}^n {E\left( {{v_{i, 3j - 2}}} \right)} , {s_j} = \prod\nolimits_{i = 1}^n {E\left( {{v_{i, 3j - 1}}} \right)} $

(4)

② 计算密文:

$ {L_j} = E\left( {IsEq\left( {{s_j}, {E_0}} \right) + \cdots + IsEq\left( {{s_j}, {E_t}} \right)} \right) $

(5)

③ 选取n个随机数 ${q_{ji}}\left( {i = 1, 2, \cdots , n} \right)$ , 计算密文数组:

$ {U_j} = \left( {{u_{j1}}, {u_{j2}}, \cdots , {u_{jn}}} \right) $

(6)

其中, ${u_{ji}}{\text{ = }}E\left( {IsEq\left( {{w_j}, {E_i}} \right) \cdot IsEq\left( {{L_j}, {E_1}} \right)} \right)$ .

(2) ${C_1}$ 将 ${Z_1} = {U_1}$ 发给 ${C_2}$ . 对于每个 $j = 2, 3, \cdots , m$ , 候选人 ${C_j}$ 收到 ${C_{j-1}}$ 发来的 ${Z_{j-1}}$ 后, 执行以下操作:

① ${C_j}$ 计算 ${Z_j}{\text{ = }}{U_j} \cdot {Z_{j-1}}$ , 其中 ${U_j} \cdot {Z_{j{\text{ - }}1}}$ 由 ${U_j}$ 和 ${Z_{j-1}}$ 对应分量相乘得到.

② ${C_j}$ 将 ${Z_j}$ 发送给 ${C_{j + 1\boldsymbolod m}}$ .

③ ${C_1}$ 最后收到密文数组

$ {Z_m} = {U_1} \cdot {U_2} \cdot\; \cdots\; \cdot {U_m}{\text{ = }}\left( {{{\textit{z}}_1}, {{\textit{z}}_2}, \cdots , {{\textit{z}}_n}} \right) $

(7)

并公开.

(3) 候选人 ${C_j}\left( {j = 1, 2, \cdots , m} \right)$ 从 $i = n$ 至 $i = 1$ 依次计算 $IsEq\left( {{{\textit{z}}_n} \cdot {{\textit{z}}_{n - 1}} \cdot \cdots \cdot {{\textit{z}}_i}, {E_k}} \right)$ , 直到找出q使式(8)成立,

$ IsEq\left( {{{\textit{z}}_n} \cdot {{\textit{z}}_{n - 1}} \cdot\; \cdots\; \cdot {{\textit{z}}_q}, {E_k}} \right){\text{ = }}1 $

(8)

停止计算.

(4) 所有人从 $i = n$ 至 $i = q$ 共同解密 ${{\textit{z}}_i}$ . 每位候选人将满足条件 $D({{\textit{z}}_i}) \ne 1$ 的i保存至集合X, 记集合 $X = \{ {x_1}, $ $ {x_2}, \cdots ,{x_e}\} \left( {1 \leqslant e \leqslant k} \right)$ .

(5) 候选人 ${C_j}\left( {j = 1, 2, \cdots , m} \right)$ 计算:

$ {Y_j} = E\left( {\sum\nolimits_{u = 1}^e {IsEq\left( {{E_0} \cdot {w_j}^{IsEq\left( {{L_j}, {E_1}} \right)}, E\left( {{x_u}} \right)} \right)} } \right) $

(9)

并公开.

(6) 所有人共同解密 $ {Y}_{j}\;\left(j=1, 2, \cdots , m\right) $ , 若 $D\left( {{Y_j}} \right) \ne 1$ , 则 ${C_j} \in W$ , 最后输出集合W.

3 方案分析与比较 3.1 正确性分析

定理1. 本方案的选举结果是正确的, 即对选民 ${P_i}\left( {i = 1, 2, \cdots , n} \right)$ 的选票 ${V_i}$ , 方案能够输出集合W.

证明: 投票阶段将其加密选票 ${B_i}$ 发送给每位候选人. 计票阶段, 所有选民和候选人利用 ${B_i}$ 进行交互计算, 输出选举结果, 其具体分析如下:

第1步. 首先, 由门限ElGamal加密系统的加法同态性, 式(4)中 $ {w_j} = \displaystyle\prod\nolimits_{i = 1}^n {E\left( {{v_{i, 3j - 2}}} \right)} {\text{ = }}E\left( {\displaystyle\sum\nolimits_{i = 1}^n {{v_{i, 3j - 2}}} } \right) $ , 同理 ${s_j} = E\left( {\displaystyle\sum\nolimits_{i = 1}^n {{v_{i, 3j - 1}}} } \right)$ , 其中 $\displaystyle\sum\nolimits_{i = 1}^n {{v_{i, 3j - 2}}} , \displaystyle\sum\nolimits_{i = 1}^n {{v_{i, 3j - 1}}} $ 分别为 ${C_j}$ 所得赞成票数和反对票数. 其次, 根据式(5)当 $\displaystyle\sum\nolimits_{i = 1}^n {{v_{i, 3j - 1}}} \gt t$ 时, ${L_j}{\text{ = }}E\left( 0 \right)$ , 此时根据式(6), 密文数组 ${U_j}$ 的分量 ${u_{ji}}\left( {i = 1, 2, \cdots , n} \right)$ 全为密文 $E\left( 0 \right)$ ; 当 $\displaystyle\sum\nolimits_{i = 1}^n {{v_{i, 3j - 1}}} \leqslant t$ 时, ${L_j}{\text{ = }}E\left( 1 \right)$ , 密文数组 ${U_j}$ 的某一个分量 $ {u_{ji}} $ 为密文 $E\left( 1 \right)$ , 其余的均为密文 $E\left( 0 \right)$ , 且若分量 ${u_{ji}} = E\left( 1 \right)$ , 表示候选人 ${C_j}$ 的赞成票数为 $i$ .

第2步. 候选人交互计算得到式(7), 其中 ${{\textit{z}}_i} = $ $ \displaystyle\prod\nolimits_{j = 1}^n {{u_{ji}}} \left( {i = 1, 2, \cdots , n} \right)$ . 由式(6)中 ${u_{ji}}$ 的计算公式知 $ {{\textit{z}}_i} = $ $ \left( {{{\text{g}}^{\displaystyle\sum\nolimits_{j = 1}^m {{q_{ji}}} }}\boldsymbolod p{\text{, }}{{\text{g}}^{\displaystyle\sum\nolimits_{j = 1}^m {IsEq\left( {{w_j}, {E_i}} \right) \cdot IsEq\left( {{L_j}, {E_1}} \right)} }}{h^{\displaystyle\sum\nolimits_{j = 1}^n {{q_{ji}}} }}\boldsymbolod p} \right) $ . 若记 ${k_i} = \displaystyle\sum\nolimits_{j = 1}^m {IsEq\left( {{w_j}, {E_i}} \right) \cdot } IsEq\left( {{L_j}, {E_1}} \right)$ , 则得赞成票数为 $i$ 的候选人有 ${k_i}$ 位.

第3步. 由于找到的 $q$ 使得式(8)成立, 根据门限ElGamal加密系统的加法同态性及协议IsEq协议可知 ${k_n}{\text{ + }}{k_{n - 1}}{\text{ + }} \cdots {\text{ + }}{k_q} = k$ . 进一步, 可知获胜的赞成票数为集合 $\left\{ {q, q + 1, \cdots , n} \right\}$ 中的元素.

第4步. 由本文使用的门限ElGamal加密系统的不完全解密性可知, $i$ 满足 $D\left( {{{\textit{z}}_i}} \right) \ne 1$ 当且仅当 ${k_i} \ne 0$ , 因此, 候选人所得集合 $X$ 由所有获胜的赞成票数构成.

第5步. 对于式(9)得到的密文 ${Y_j}$ , 根据门限ElGamal加密系统的加法同态性, 若候选人 ${C_j}$ 的反对票数没有超过阈值t且赞成票数与某个获胜票数相等时, ${Y_j} = $ $ E\left( 1 \right)$ ; 否则 ${Y_j} = E\left( 0 \right)$ . 再由此加密系统的不完全解密性可知, 当 $D\left( {{Y_j}} \right) \ne 1$ 时, 候选人 ${C_j}$ 获胜.

第6步. 结束时所有获胜候选人将被输出.

综上所述, 该方案的选举结果是正确的.

3.2 全隐私性分析

全隐私性^[10]是指在整个选举过程中, 所有选民的选票信息和候选者的得票数均是隐私的.

定理2. 在半诚实模型下, 本方案满足对所有选民选票信息的隐私保护.

证明: 由于任意n–1位选民和所有的候选者合谋, 可以产生最大程度的攻击. 因此, 在此合谋结构下, 证明方案满足对所有选民投票信息的隐私保护即可. 此处用模拟范例^[19]的方法证明. 由于每位选民的地位是平等的, 不妨设选民 ${P_1}, {P_2}, \cdots , {P_{n - 1}}$ 和所有候选者 ${C_1}, {C_2}, \cdots , {C_m}$ 合谋获得 ${P_n}$ 的选票 ${V_n}$ , 记合谋者构成的集合为 $\tau = \left\{ {{P_1}, \cdots , {P_{n - 1}}, {C_1}, \cdots , {C_m}} \right\}$ . 对于 $\tau $ 中的参与者, 需构造相应的模拟器S使式(10)成立.

$ \left\{ {S\left( {{V_1}, {V_2}, \cdots , {V_{n - 1}}, W} \right)} \right\}\mathop \equiv \limits^c \left\{ {VIEW_\tau ^\pi \left( {{V_1}, {V_2}, \cdots , {V_n}} \right)} \right\} $

(10)

S构造门限ElGamal加密系统, 其主私钥为 ${x'}$ , 对应的公钥为 ${h'}$ . 用此加密系统的公钥计算密文 $E_s'= $ $ E'(s)= \left( g^r \mod\;p,g^s h'^r\mod p\right)(s=1,2,\cdots,n)$ , S接收输入 $\left\{ {{V_1}, {V_2}, \cdots , {V_{n - 1}}, W} \right\}$ , 按如下方式运行:

(1) $S$ 构造一个数组 ${V_n}' = \left( {v_{n, 1}', v_{n, 2}', \cdots , v_{n, 3m}'} \right)$ , 使得 $\pi \left( {{V_1}, {V_2}, \cdots , {V_{n - 1}}, {V_n}'} \right) = W$ .

(2) $S$ 利用数组 ${V_1}, {V_2}, \cdots , {V_{n - 1}}, {V_n}'$ 模拟投票阶段, 计算得到加密选票 ${B_1}, {B_2}, \cdots , {B_{n - 1}}, B_n'$ , 其中 ${B_{n'}} = (E\left( {{v_{n,{1^\prime }}}} \right), $ $ E\left( {{v_{n,{2^\prime }}}} \right), \cdots ,E\left( {{v_{n,3{m^\prime }}}} \right))$ .

(3) $S$ 利用 ${B_1}, {B_2}, $ $ \cdots , {B_{n - 1}}, B_n'$ 模拟计票阶段. 执行第1步得 $\left\{ {w_j', s_j', L_j', q_{ji}', U_j'} \right\}$ , 其中 $j = 1, 2, \cdots , m, $ $i = 1, 2, \cdots , n$ , $w_j'$ 和 $s_j'$ 为密文, $q_{ji}'$ 为随机数, $U_j'$ 为密文数组. 执行第2步得密文数组 $Z_m' = \left( {{\textit{z}}_1', {\textit{z}}_2', \cdots , {\textit{z}}_n'} \right)$ . 进一步, $S$ 按照第3、4步计算得 ${q'}$ 和集合 ${X'} = \left\{ {x_1', x_2', \cdots , x_e'} \right\}$ $(1 \le e \le k)$ . 继续执行第5、6步, 计算得密文 $Y_j'$ , 解密 $Y_j'$ 并输出 $W'$ . 综上, $S$ 在模拟过程中得到的信息序列为:

$ \begin{split} &\left\{ {S\left( {{V_1}, {V_2}, \cdots , {V_{n - 1}}, W} \right)} \right\} {\text{ = }}\\ &\left\{ {{V_1}, {V_2}, \cdots , {V_{n - 1}}, w_j', s_j', q_{ji}', L_j', U_j', {Z_m}', {q'}, {X'}, Y_j', W'} \right\} \end{split} $

(11)

其中, $j=1, 2, \cdots , m,\;i=1, 2, \cdots , n, \;{W}' =\pi ({V}_{1}, \cdots , {V}_{n-1}, {V}_{n}{}^{{'}})$ .

而在整个方案执行过程中:

$ \begin{split} &VIEW_\tau ^\pi \left\{ {{V_1}, {V_2}, \cdots , {V_n}} \right\} = \\ &\left\{ {{V_1}, {V_2}, \cdots , {V_{n - 1}}, {w_j}, {s_j}, {q_{ji}}, {L_j}, {U_j}, {Z_m}, q, X, {Y_j}, W} \right\} \end{split} $

(12)

其中, $j=1, 2, \cdots , m,\; i=1, 2, \cdots , n$ .

由于门限ElGamal加密系统具有语义安性, 因此, 对于 $\tau $ 中所有参与者而言有:

$ \left\{ {w_j', s_j', L_j', U_j', {Z_m}', Y_j'} \right\}\mathop \equiv \limits^c \left\{ {{w_j}, {s_j}, {L_j}, {U_j}, {Z_m}, {Y_j}} \right\} $

其中, $j{\text{ = }}1, 2, \cdots , m$ . 因为随机数计算不可区分, 则 $r_{j, i}'\mathop \equiv \limits^c {r_{j, i}}$ , 其中 $ j=1, 2, \cdots , m, $ $i=1, 2, \cdots , n$ . 根据 ${q'}$ 和集合 ${X'}$ , $\tau $ 中所有参与者不能推断出选民 ${P_n}$ 的隐私信息 ${V_n}$ , 且 $ W'{\text{ = }}\pi \left( {{V_1}, {V_2}, \cdots , {V_{n - 1}}, {V_n}'} \right) = W $ , 因此式(13)成立.

$ \left\{ {S\left( {{V_1}, {V_2}, \cdots , {V_{n - 1}}, W} \right)} \right\}\mathop \equiv \limits^c \left\{ {VIEW_\tau ^\pi \left( {{V_1}, {V_2}, \cdots , {V_n}} \right)} \right\} $

(13)

定理2得证, 即本方案满足对选民选票信息的隐私保护.

由于本方案仅输出获胜候选人的名单, 且即使在计票阶段每位候选人保存了获胜候选者对应的获胜票数, 但其无法将票数与候选人对应起来, 则方案满足对获胜者得票数的隐私保护. 同时, 由于门限ElGamal加密系统的特性, 任何人都无法解密式(4)中的 ${w_j}, {s_j}$ , 因此无法得到落选者的得票数, 即方案满足对落选者得票数的隐私保护.

综上, 本方案满足全隐私性, 并且保护了所有落选者的得票数.

3.3 其它安全性质分析

(1)无收据性是指任何选民都无法向他人证明自己的选票. 本方案中每位选民将加密选票发送给所有候选人, 由于门限ElGamal加密系统的特性, 选民靠自己不能解密任何密文, 则无法向候选人证明自己的选票.

(2)公平性是指所有选民同时得到选举结果. 该方案的选举结果在计票阶段结束之后输出, 任何人都无法提前获知选举结果. 因此, 本方案满足公平性.

3.4 复杂性分析与比较

本文设计的方案使用了门限ElGamal加密系统, 分析时只考虑费时的模指数运算, 每次加密操作需要2次模指数运算, 每次解密操作需要 $n + m + 1$ 次模指数运算.

投票阶段, 所有选民需要 $3nm$ 次加密. 计票阶段, 所有选民和候选人最多执行 $m\left( {n + 2{\text{ + }}k} \right)$ 次加密和 $m + k$ 次解密. 因此投票阶段和阶段最多需要模指数运算 $2\left[ {3nm + m\left( {n + 2{\text{ + }}k} \right)} \right] + \left( {m + k} \right)\left( {n + m + 1} \right)$ 次. 计票阶段, 最多需要调用 $m\left( {3n + 2k + t{\text{ + }}1} \right)$ 次IsEq协议, 根据文献[23], 本文执行IsEq协议所需模指数运算复杂度 ${\rm{O}}\left( {{n^2}m} \right)$ . 综上所述, 本方案的计算复杂度为 ${\rm{O}}\left( {{n^2}m} \right)$ .

将本文设计的方案与文献[6,7]中提出的全隐私多候选人电子投票方案进行对比, 如表2所示. 本方案考虑了候选者所得反对票数, 且其全隐私性实现了对所有候选者得票数的保护.

4 结语

为使选举结果更符合选民的意愿, 本文首次考虑了候选人反对票数. 在此基础上提出了一个满足全隐私性、无需第三方参与的多选多电子投票方案, 并且本方案的全隐形实现了对所有候选人得票数的保护. 此外, 分析表明方案同时满足公平性和无收据性. 下一步工作将研究符合实际应用场景需求、满足更多安全性质且高效的电子投票方案.