﻿ 基于同态加密的多候选人电子投票方案
 计算机系统应用  2019, Vol. 28 Issue (2): 146-151 PDF

Multi-Candidate Electronic Voting Scheme Based on Homomorphic Encryption
HE Qian, SHEN Wei
School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China
Abstract: Electronic voting is increasingly popular because of its convenience. However, the security problems exposed in electronic voting have become the focus of attention. How to ensure anonymity and verifiability in electronic voting has become a concern. Aiming at various problems in existing electronic voting, a multi-candidate electronic voting scheme is proposed based on digital signature algorithm and full homomorphic encryption. This scheme uses elliptic curve digital signature algorithm to solve the problem of identity authentication in electronic voting. The homomorphic encryption technology is used to realize the encryption of votes and homomorphism calculation of encrypted votes. To be able to batch votes, SIMD technology is used to packing votes. A homomorphic addition ticket counter was designed for the codec problem of encrypted votes counting. Finally, the security of the scheme is analyzed based on the eight security features of electronic voting, which shows that the scheme is safe and feasible.
Key words: electronic voting     digital signature     full homomorphic encryption     SIMD     homomorphic addition ticket counter

1 预备知识 1.1 数字签名算法

 图 1 ECDSA原理图

1.2 全同态加密算法

 图 2 全同态加密原理图

2009年Gentry构造出了第一个全同态加密方案[11], 随即掀起了全同态研究的热潮, 大量的跟进工作随即出现, 其中具有代表性的全同态加密方案有: 基于整数上的DGHV方案[12]、基于RLWE的BGV方案[13]以及基于近似特征向量的GSW方案[14].

1.2.1 LWE问题

DLWE问题定义: 安全参数 $\lambda$ , 参数 $n: = n(\lambda ) \in {\bf{Z}}$ , 模 $q: = q(\lambda ) \geqslant 2 \in {\bf{Z}}$ , 错误分布 $\chi : = \chi (\lambda ) \in {\bf{Z}}$ . $DLW{E_{n, q, \chi }}$ 问题是区分如下两种分布: 第一种分布, LWE样本 $({{{a}}_i}, {b_i})$ 是从 ${\bf{Z}}_q^n \times {{\bf{Z}}_q}$ 中随机取样得到; 第二种分布, ${{s}}\xleftarrow{U}{\bf{Z}}_q^n$ , 样本 $({{{a}}_i}, {b_i})$ 是通过以下方式得到: 均匀采样 ${{{a}}_i}\xleftarrow{U}{\bf{Z}}_q^n$ , ${{{e}}_i}\xleftarrow{R}\chi$ , 令 ${b_i}: = < {{{a}}_i}, {{s}} > + {e_i}od q$ .

1.2.2 RAO-GSW算法

RAO-GSW全同态加密算法[15]由五个算法组成, 分别为: Setup、KeyGen、Encrypt、Decrypt和Evaluate.

1) Setup( $\lambda$ ): 安全参数 $\lambda$ , 格维 $n: = n(\lambda ) \in {\bf{Z}}$ , 模 $q: = q(\lambda ) \geqslant 2 \in {\bf{Z}}$ , 错误分布 $\chi : = \chi (\lambda ) \in {\bf{Z}}$ , 参数 $\ell = \left\lceil {\log q} \right\rceil$ , $m: = O(n + r)\log q$ , $N: = (n + r) \cdot \ell$ , 其中 $r$ 为要加密的比特数, 定义明文空间为 ${\left\{ {0, 1} \right\}^{r \times r}}$ , 密文空间为 ${\bf{Z}}_q^{(n + r) \times N}$ . ${{{g}}^{\rm{T}}} = (1, 2, \cdots, {2^{\ell - 1}})$ , ${\bf{G}} = {{{g}}^{\rm{T}}} \otimes {{{I}}_{n + r}}$ , $\otimes$ 代表张量积.

2) KeyGen( ${1^\lambda }, r$ ): 随机均匀采样矩阵 ${{A}}\xleftarrow{U}{\bf{Z}}_q^{n \times m}$ , 私钥矩阵 ${{{S}}'}\xleftarrow{R}{\chi ^{r \times n}}$ , 噪声矩阵, 设 ${{E}}\xleftarrow{R}{\chi ^{r \times m}}$ , 设

 ${{S}}: = \left[ {{{{I}}_r}|| - {{{S}}'}} \right] \in {\bf{Z}}_q^{r \times (n + r)}$ (1)

 ${{B}}: = \left( {\frac{{{{{s}}'}{{A}} + {{E}}}}{{{A}}}} \right) \in {\bf{Z}}_q^{(n + r) \times m}$ (2)

 ${{{P}}_{(i, j)}}: = {{B}}{{{R}}_{(i, j)}} + \left( {\frac{{{{{M}}_{(i, j)}}{{S}}}}{0}} \right){{G}} \in {\bf{Z}}_q^{(n + r) \times N}$ (3)

3) $En{c_{pk}}({{M}} \in {\left\{ {0, 1} \right\}^{r \times r}})$ , 随机均匀采样矩阵 ${{R}}\xleftarrow{U}{\left\{ {0, 1} \right\}^{m \times N}}$ , 输出密文如下:

 ${{C}}: = \left( {{{BR}} + \sum\nolimits_{i, j \in [r];M[i, j] = 1} {{{{P}}_{(i, j)}}} } \right) \in {\bf{Z}}_q^{(n + r) \times N}$ (4)

4) $De{c_{sk}}({{C}})$ :

 ${{SC}} = {{E}} + {{MSG}}(od q)$ (5)

 ${{M}} = {\left( {{{\left\lceil {\left\langle {{{{s}}_i}, {{{c}}_{j\ell - 1}}} \right\rangle } \right\rceil }_2}} \right)_{i, j \in [r]}} \in {\left\{ {0, 1} \right\}^{r \times r}}$ (6)

5) Evaluate算法包括两种: 同态加法和同态乘法.

① Add: 设输入两个密文 ${{{C}}_1}$ ${{{C}}_2}$ , 则有:

 ${{{C}}_{\rm{add}}}: = {{{C}}_1} + {{{C}}_2} \in {\bf{Z}}_q^{(n + r) \times N}$ (7)

② Mult: 设输入两个密文 ${{{C}}_1}$ ${{{C}}_2}$ , 则有:

 ${{{C}}_{\rm{mult}}}: = {{{C}}_1}{{{G}}^{ - 1}}({{{C}}_2}) \in {\bf{Z}}_q^{(n + r) \times N}$ (8)

6)方案安全性

2 同态计票器 2.1 进位溢出问题

 ${{\bf{Z}}^ + }\mathop {\longleftrightarrow}\limits^{{\text{编解码}}}{\left\{ {0, 1} \right\}^{r \times r}}\mathop {\longleftrightarrow}\limits^{{\text{RAO-GSW方案}}}{\bf{Z}}_q^{(n + r) \times N}$

2.2 同态计票器原理与设计

${a_1}, {a_2} \in \left\{ {0, 1} \right\}$ , 记 $\oplus$ 为模二加法, $\otimes$ 为模二乘法. 令 $s = {a_1} \oplus {a_2}$ , $c = {a_1} \otimes {a_2}$ , 则 $sum = {a_1} + {a_2}= 2c + s$ .

 $s = \mathop \oplus \limits_{i = 1}^n {a_i}$
 ${c^{(j)}} = {s^{(j - 1)}} \otimes {a_j},$
 ${s^{(j)}} = \mathop \oplus \limits_{i = 1}^n {a_i}, j = 2, 3, \cdots, n$

 $sum = {a_1} + {a_2} + \cdot \cdot \cdot + {a_n} = 2\left( {\sum\nolimits_{j = 2}^n {{c^{(j)}}} } \right) + s$ (9)
 图 3 多比特计票器

 ${{{M}}_i} = \left( {\begin{array}{*{20}{c}} {m_1^{(i)}}&{\begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {}&{} \end{array}} \end{array}} \\ {\begin{array}{*{20}{c}} {} \\ {} \\ {} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {m_2^{(i)}} \\ {} \\ {} \end{array}}&{\begin{array}{*{20}{c}} {} \\ \ddots \\ {} \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {} \\ {} \\ {m_u^{(i)}} \end{array}} \end{array}} \end{array}} \right)$

 $sum = {M_1} + {M_2} + \cdot \cdot \cdot + {M_v}\\ = 2(\sum\nolimits_{j = 2}^v {{{{C}}^{(j)}}} ) + {{S}}$ (10)

 ${{S}} = \mathop \oplus \limits_{i = 1}^v {M_i}$
 ${{{C}}^{(j)}} = {{{S}}^{(j - 1)}} \otimes {{{M}}_{(j)}}, j = 2, 3, \cdots, v$
 ${{{S}}^{(j)}} = \mathop \oplus \limits_{i = 1}^j {{{M}}_i}$

3 全同态加密多候选人电子投票方案 3.1 方案描述

 图 4 方案实体交互图

3.2 系统初始化

① 选择一个随机数 $k, k \in [1, n - 1]$ ;

② 计算 $kG = ({x_1}, {y_1})$ ;

③ 计算 $r = {x_1}od n$ , 如果 $r = 0$ , 则跳转到第一步;

④ 计算 $e = H(m)$ ;

⑤ 计算 $s = {k^{ - 1}}(e + dr)od n$ , 如果 $s = 0$ , 则跳转到第一步;

⑥ 对消息 $m$ 的签名为 $(r, s)$ .

① 检验 $r, s \in [1, n - 1]$ , 若不成立, 返回拒绝签名;

② 计算 $e = H(m)$ ;

③ 计算 ${u_1} = e{s^{ - 1}}od n, {u_2} = r{s^{ - 1}}od n$ ;

④ 计算 $X = {u_1}G + {u_2}Q = ({x_1}, {y_1})$ , 如果 $X =$ 零点, 则验证改签名无效;

⑤ 计算 $v = {x_1}od n$ ;

⑥ 如果 $v = r$ , 则签名有效, 否则签名无效.

3.3 注册阶段

 $I{D_{{V_i}}}||{B_{{V_i}}}||SI{G_R}(I{D_{{V_i}}}||{B_{{V_i}}})$

3.4 投票阶段

 $\left( {\begin{array}{*{20}{c}} {{m_1}}&{}&{}&{\begin{array}{*{20}{c}} {}&{} \end{array}} \\ {}& \ddots &{}&{\begin{array}{*{20}{c}} {}&{} \end{array}} \\ {}&{}&{{m_i}}&{\begin{array}{*{20}{c}} {}&{} \end{array}} \\ {\begin{array}{*{20}{c}} {} \\ {} \end{array}}&{\begin{array}{*{20}{c}} {} \\ {} \end{array}}&{\begin{array}{*{20}{c}} {} \\ {} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} \ddots &{} \end{array}} \\ {\begin{array}{*{20}{c}} {}&{{m_r}} \end{array}} \end{array}} \end{array}} \right) \in {\left\{ {0, 1} \right\}^{r \times r}}$

 ${{C}} = {{BR}} + \sum\limits_{i, j = [r];M[i, j] = 1} {{{{P}}_{(i.j)}}}$

 $I{D_{{V_i}}}||{B_{{V_i}}}||p{k_o}||{C_i}||SI{G_O}(I{D_{{V_i}}}||{B_{{V_i}}})$

 $S||C^{(i)}||SI{G_V}(I{D_{{V_i}}}||{B_{{V_i}}}||{C_i})$
3.5 计票阶段

4 安全性分析

(1)合法性. 在注册阶段每位投票人都会使用自己的身份材料去注册中心进行注册, 注册中心会对投票人的身份信息进行审核, 只有通过审核的投票人才能参与投票.

(2)匿名性. 首先在投票人通过注册中心的审核后, 注册中心会给投票人发放一个和自己身份信息无关的身份标识, 这样很好的隐藏了投票人的真实身份信息; 其次, 在投票阶段, 投票人利用同态加密方案中的公钥对选票进行加密, 因此, 除了投票人本身, 其他任何人都不能通过加密的选票获得选票的真实内容, 也不能将选票和投票人的身份对应起来.

(3)唯一性. 首先在注册阶段, 通过注册中心认证的合法投票人会获得唯一投票标识, 因此, 每位投票人只拥有一次投票机会.

(4)公正性. 在本方案中, 投票私钥由计票中心持有, 计票中心在计算选票之后, 使用该私钥进行解密, 得到最终结果. 由于同态加密算法是对于密文进行计算, 因此该计算可交给任何一个可信第三方, 因此保证了方案的公正性.

(5)完备性. 在投票阶段, 投票中心首先会根据注册中心的信息对投票人的身份进行认证, 保证投票人身份合法, 其次会根据投票人的投票编号来检查选票的唯一性, 而且通过使用数字签名技术可以对选票内容的完整性进行验证, 只有全部通过上述认证的选票才会被投票中心正确的统计, 如若有一项没有通过验证, 则会被丢弃, 最终的计票结果只会统计合法选票.

(6)可验证性. 在投票阶段, 投票中心将收集到的选票公布在了公示中心, 每位投票人都可以根据公告栏上的信息和自己持有的信息进行比对, 以确认自己的选票是否有被正确统计.

(7)正当性. 方案的每个阶段都会进行身份认证来防止恶意的投票者破坏投票.

(8)无争议性. 由于本方案是基于ECDSA和全同态加密, 因此方案的安全性是可证明的, 方案中的各方的公钥都是公开的, 任何投票人或第三方都可验证方案过程的正确性.

5 结束语

 [1] Lee B, Boyd C, Dawson E, et al. Providing receipt-freeness in mixnet-based voting protocols. In: Lim JI, Lee DH, eds. Information Security and Cryptology–ICISC 2003. Berlin, Heidelberg: Springer, 2004. 245–258. [2] Chaum D, Ryan PYA, Schneider S. A practical voter-verifiable election scheme. In: De Capitani Di Vimercati S, Syverson P, Gollmann D, eds. Computer Security–ESORICS 2005. Berlin, Heidelberg: Springer, 2005. 118–139. [3] Fujioka A, Okamoto T, Ohta K. A practical secret voting scheme for large scale elections. Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology. Queensland, Australia. 1992. 244–251. [4] Radwin MJ. An untraceable, universally verifiable voting scheme. Seminar in Cryptology. 1995. http://www.radwin.org/michael/project/voting.pdf. [5] Kim K, Kim J, Lee B, et al. Experimental design of worldwide internet voting system using PKI. SSGRR, 2001. [6] 杨婷婷, 林昌露, 张胜元. 安全的多候选人电子投票方案的改进. 福建师大学报(自然科学版), 2015, 31(3): 32-38. [7] Anggriane SM, Nasution SM, Azmi F. Advanced e-voting system using Paillier homomorphic encryption algorithm. 2016 International Conference on Informatics and Computing. Mataram, Indonesia. 2017. 338–342. [8] 黄仕杰, 洪璇. 基于同态实现多候选人的电子投票方案. 计算机应用与软件, 2017, 34(3): 284-288. DOI:10.3969/j.issn.1000-386x.2017.03.051 [9] 朱正阳, 刘镪, 唐春明, 等. 基于LWE同态加密的电子投票方案. 信息网络安全, 2013(5): 8-11. DOI:10.3969/j.issn.1671-1122.2013.05.003 [10] Johnson D, Menezes A, Vanstone S. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security, 2001, 1(1): 36-63. DOI:10.1007/s102070100002 [11] Gentry C. Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. Bethesda, MD, USA. 2009. 169–178. [12] Van Dijk M, Gentry C, Halevi S, et al. Fully homomorphic encryption over the integers. Gilbert H. Advances in Cryptology–EUROCRYPT 2010. Berlin, Heidelberg: Springer, 2010. 24–43. [13] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge, MA, USA. 2012. 309–325. [14] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Canetti R, Garay JA. Advances in Cryptology (CRYPTO 2013). Berlin, Heidelberg: Springer, 2013. 75–92. [15] Hiromasa R, Abe M, Okamoto T. Packing messages and optimizing bootstrapping in GSW-FHE. In: Katz J, ed. Public Key Cryptography (PKC 2015). Berlin, Heidelberg: Springer, 2015. 699–715. [16] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. Baltimore, MD, USA. 2005. 84–93. [17] 王永恒, 徐晨, 陈经纬, 等. 基于HElib的安全电子投票方案. 计算机应用研究, 2017, 34(7): 2167-2171. DOI:10.3969/j.issn.1001-3695.2017.07.055