An E-Voting Protocol Based on Multi-Key Homomorphic Encryption

doi:10.3969/j.issn.1671-1122.2025.01.008

Abstract

Abstract:

The e-voting scheme receives more and more attention due to its efficiency and accuracy of results. However its security has always been the bottleneck. This paper introduced an E-voting protocol that leveraged a multi-key homomorphic encryption algorithm without ciphertext expansion. The protocol enabled the verification of vote legitimacy and the counting of votes on encrypted data, culminating in the use of distributed decryption to announce the election outcomes. The multi-key homomorphic encryption algorithm without ciphertext extension could ensure the anonymity and security of a voter’s identity and balloted throughout the full cycle. Also each balloted has nothing to do with the number of participants, thereby the protocol guaranteed the validity of the E-voting protocol. Though theoretical proofs, this paper demonstrates that based on multi-key homomorphic encryption, the E-voting protocol encompasses various security features and correctness.

Key words: E-voting, homomorphic encryption, multi-key homomorphic encryption

CLC Number:

TP309

ZHANG Yang, WEI Rong, YOU Qidi, JIANG Xiaotong. An E-Voting Protocol Based on Multi-Key Homomorphic Encryption[J]. Netinfo Security, 2025, 25(1): 88-97.

Figures/Tables 8

符号	含义
$n$	理想格的维数
$\mathbf{Z}\mathbf{R}$	分别表示整数集和实数集
$a(x)$	多项式表示
$a$	向量表示
$\mathbf{Z}[x]$	整系数多项式环
$\left\langle a\left( x \right) \right\rangle $	多项式$a(x)$在$\mathbf{Z}[x]$中生成的理想
$R$	多项式环$\mathbf{Z}[x]/\left\langle \phi \left( x \right) \right\rangle $
${{R}_{q}}$	${{R}_{q}}=R/qR$，每个多项式的系数都在$\left[ -{}^{q}/{}_{2},{}^{q}/{}_{2} \right]$中
$a[i]$	给定$a=\left( {{a}_{0}},{{a}_{1}},\cdots,{{a}_{n-1}} \right)\in {{\mathbf{R}}^{n}}$，$a[i]={{a}_{i-1}}$，给定$a=\left( {{a}_{0}},{{a}_{1}} \right)\in R_{q}^{2}$，$a[i]={{a}_{i-1}}$
$\left\\| \cdot \right\\|$	${{l}_{\infty }}$范数，针对多项式$a(x)=\sum\limits_{i=0}^{n-1}{{{a}_{i}}{{x}^{i}}}$，定义为$\left\\| a(x) \right\\|=\underset{0\le i\le n-1}{\mathop{\max }}\,\left\| {{a}_{i}} \right\|$ 针对$a=\left( {{a}_{0}},{{a}_{1}},\cdots,{{a}_{n-1}} \right)$，定义为$\left\\| a \right\\|=\underset{0\le i\le n-1}{\mathop{\max }}\,\left\| {{a}_{i}} \right\|$
$\delta $	环$R$扩展因子，定义为$\delta =\underset{a,b\in R}{\mathop{\max }}\,\left\{ \frac{\left\\| a(x)\cdot b(x) \right\\|}{\left\\| a(x) \right\\|\cdot \left\\| b(x) \right\\|} \right\}$
$\|\|$	给定$a=\left( {{a}_{0}},{{a}_{1}},\cdots,{{a}_{n-1}} \right)$和$b=\left( {{b}_{0}},{{b}_{1}},\cdots,{{b}_{n-1}} \right)$，定义$a\|\|b=\left( {{a}_{0}},\cdots,{{a}_{n-1}},{{b}_{0}},\cdots,{{b}_{n-1}} \right)$
$a$	数$a$的四舍五入
$\chi $	离散高斯采样分布
$\left[ -B,B \right]$	分布$\chi $的支撑集
$L$	格
${{\left[ a \right]}_{q}}$	${{\left[ a \right]}_{q}}=a\bmod q\in \left[ -\frac{q}{2},\frac{q}{2} \right]$
$H(\cdot )$	杂凑函数，在具体方案中可选择不同的杂凑函数来实现
$N$	电子投票参与人数
$q$	密文模数
$l$	明文模数
$T$	候选者人数
$t$	当选者人数
${{m}_{i}}$	投票者$i$的明文（选票）
$m$	对各参与方进行同态计算后对应的明文
$ct$	密文
$s{{k}_{i}}$	投票者$i$的私钥
$sk$	联合私钥，要求$sk=\sum\limits_{i=1}^{N}{s{{k}_{i}}}$
$p{{k}_{i}}$	投票者$i$的公钥
$pk$	联合公钥，要求$pk[0]=\sum\limits_{i=1}^{N}{p{{k}_{i}}[0]}$
$Add(\cdot )$	密文加法运算
${{p}_{i}}$	投票者$i$的部分解密

References 16

[1]	CHAUM D L. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms[J]. Communications of the ACM, 1981, 24(2): 84-90.
[2]	CHAUM D. Blind Signatures for Untraceable Payments[C]// Springer. Advances in Cryptology. Heidelberg: Springer, 1983: 199-203.
[3]	FUJIOKA A, OKAMOTO T, OHTA K. A Practical Secret Voting Scheme for Large Scale Elections[C]// Springer. Lecture Notes in Computer Science. Heidelberg: Springer, 1993: 244-251.
[4]	SCHOENMAKERS B. A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting[C]// Springer. Lecture Notes in Computer Science. Heidelberg: Springer, 1999: 148-164.
[5]	DAMGÅRD I, JURIK M. A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System[C]// Springer. Lecture Notes in Computer Science. Heidelberg: Springer, 2001: 119-136.
[6]	DAMGÅRD I, GROTH J, SALOMONSEN G. The Theory and Implementation of an Electronic Voting System[C]// Springer. Advances in Information Security. Heidelberg: Springer, 2003: 77-99.
[7]	ZHU Guocheng, HE Debiao, AN Haoyang, et al. Proxy Voting Scheme Based on Blockchain and SM9 Digital Signature[J]. Netinfo Security, 2024, 24(1): 36-47.
	朱郭诚, 何德彪, 安浩杨, 等. 基于区块链和SM9数字签名的代理投票方案[J]. 信息网络安全, 2024, 24(1): 36-47.
[8]	YANG Yatao, LIU Deli, LIU Peihe, et al. BFV-Blockchainvoting: Blockchain-Based Electronic Voting Systems with BFV Full Homomorphic Encryption[J]. Journal on Communications, 2022, 43(9): 100-111. doi: 10.11959/j.issn.1000-436x.2022172
	杨亚涛, 刘德莉, 刘培鹤, 等. BFV-Blockchainvoting:支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111. doi: 10.11959/j.issn.1000-436x.2022172
[9]	LI Yawei, WANG Weiqiong, XIE Qiong. Multi-Candidate Electronic Voting Scheme Based on Secure Multi-Party Computation[J]. Computer Systems & Applications, 2022, 31(4): 386-391.
	李亚伟, 王维琼, 谢琼. 基于安全多方计算的多候选人电子投票方案[J]. 计算机系统应用, 2022, 31(4): 386-391.
[10]	YIN Hongjian, ZHU Yan, WANG Jing, et al. Design and Implementation of a Smart-Contract Voting System Based on Zero-Knowledge Proof[J]. Chinese Journal of Engineering, 2023, 45(4): 632-642.
	殷红建, 朱岩, 王静, 等. 基于零知识证明的智能合约投票系统设计与实现[J]. 工程科学学报, 2023, 45(4): 632-642.
[11]	MENG Bo, WANG Dejun. Secure Remote Network Voting Protocol[M]. Beijing: Science Press, 2013.
	孟博, 王德军. 安全远程网络投票协议[M]. 北京: 科学出版社, 2013.
[12]	NEWTON P, RICHELSON S. A Lower Bound for Proving Hardness of Learning with Rounding with Polynomial Modulus[C]// Springer. Lecture Notes in Computer Science. Heidelberg: Springer, 2023: 805-835.
[13]	RIVEST R, ADLEMAN L, DERTOUZOS M. On Data Banks and Privacy Homomorphisms[EB/OL]. [2024-10-10]. https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/RAD78.pdf.
[14]	LÓPEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption[C]// ACM. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing. New York: ACM, 2012: 1219-1234.
[15]	FAN Junfeng, VERCAUTEREN F. Somewhat Practical Fully Homomorphic Encryption[EB/OL]. (2012-03-22)[2024-10-10]. https://eprint.iacr.org/2012/144.
[16]	DAZA V, MORILLO P, ROVIRA S. Leveled Multikey FHE with Constant-Size Ciphertexts from RLWE[EB/OL]. (2022-04-12)[2024-10-10]. https://eprint.iacr.org/2022/447.

方案	秘密性	不可重用性	适格性	公平性	可验证性	全周期隐私性
文献[7]方案	√	×	√	√	√	×
文献[8]方案	√	√	√	√	√	×
文献[9]方案	√	√	√	√	×	√
本文方案	√	√	√	√	√	√