基于全同态加密电子投票方案的研究

Research Based on Fully Homomorphic Encrypted Electronic Voting Scheme

摘要: 本文提出了一种能够进行任意次加乘运算的基于无噪声的全同态加密算法，以及椭圆曲线数字签名算法等技术来实现安全的电子投票方案，并给出了方案的安全性分析。该方案较好地解决了电子投票中的匿名性、完整性和公开可验证性难题，实现了安全、公开、公平和公正的电子投票。

Abstract: This paper proposes a noise-free fully homomorphic encryption algorithm capable of performing arbitrary multiplication operations, and an elliptic curve digital signature algorithm to implement a secure e-voting scheme, and gives a security analysis of the scheme. The scheme solves the prob-lems of anonymity, integrity and public verifiability in e-voting, and achieves secure, open, fair and just e-voting.

1. 引言

随着电子商务、电子选举、电子货币的普及，人们对公开网络所传输数据的安全性提出了更高要求，于是，全同态加密走进了人们的视野 [1]。同态加密最早是由Rivest [2] 三人提出的，即在不知道加密密钥的情况下，对密文进行计算，其结果与明文作相同计算的结果相同。40多年以来，人们提出的加密方案大多只满足加法同态或乘法同态，同时还有一些能够同时满足有限次加法与乘法的同态方案。直到2009年，由Gentry等人才构造出第一个真正意义上的全同态加密方案 [3] [4]。在此文中，构造了一个可实现有限次同态计算的Some What方案，通过同态解密来实现密文的更新，从而实现全同态加密。但缺点是同态解密的效率低，复杂度相对较高 [5] [6]。

近年来，人们基于Gentry的方案产生了许多全同态加密方案及优化。Dijk等人提出了基于整数的全同态加密方案，称为DGHV方案，其完全基于整数上的算术运算，概念简单，易于理解，但缺点是计算复杂并且易受噪声的干扰 [7]。于是本文从另外一个方面考虑，提出了一个没有噪声的全同态加密方案，该方案概念简单、易于理解，计算易于实现且不会受噪声干扰。

本文针对计票过程中存在的安全问题，面向中大型投票场景，综合采用全同态加密(FHE)、数字签名，设计实现了一个具有更高安全性保障的电子投票系统，并在保证安全的前提下，尽可能地提高了系统的性能 [8] [9] [10]。针对电子投票中存在的问题，引入了椭圆曲线数字签名算法，签名速度更快，更适用于电子投票场景，能更好地解决电子投票中的身份认证问题。从初始化、注册投票、计票和验证查票四个阶段详细阐述了电子投票方案的具体流程。

2. 相关算法

2.1. 无噪声的全同态加密方案

2.1.1. 算法描述

目前提出的方案在进行同态运算时会受到噪声的干扰，这会影响运算速度，在大数据和云计算的环境下有很大的局限性，本文基于文献 [8] 在没有噪声的全同态加密基础上，提出了一个改进的无噪声全同态加密方案，提高了计算效率和安全性。

2.1.2. 具体方案

1) KeyGen：p和q是两个比较大的素数且占 $\lambda$ bits ( $\lambda =512$ )，h是一个小的正数( $h\ge 2$ )，令 $N=pq$，其中h和N是公开的，p和q是保密的。

h的约束条件：

初始化一个计数器和计时器，用来记录加密的次数和密钥的有效周期。

① 加密的次数小于h，则不用更新密钥K；

② 加密 $h-1$ 次后，重新分配密钥 $K_1\left(K_1\ne K\right)$ ；

③ 密钥K在一个有效周期内最多允许加密 $h-1$ 次，完成 $h-1$ 次加密后，则立即更新密钥K，并重新计时；

④ 当需要加密的次数为 $Y\left(Y>h\right)$ 次时，则密钥K可以变为 $\left(x_1,x_2,\cdots ,x_{h_1}\right)$ ( $h_1>Y$ )。

明文的集合是 ${\mathbb{Z}}_p$，故所有加法或乘法的结果始终是集合 $\left\{0,1,\cdots ,p-1\right\}$ 中的整数，又因为 $N=pq$，p是保密的，故在进行操作时，可直接对N取模。

密文的集合是有限的向量空间 ${\mathbb{Z}}_p^h$，故所有的密文形式为 $\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)$，且 $\forall i\in \left(1,2,\cdots ,h\right)$， $h{\alpha }_i\in {\mathbb{Z}}_N\cdot {\mathbb{Z}}_N^h$。密钥 $K=\left(x_1,x_2,\cdots ,x_h\right)\in {\mathbb{Z}}_N^h$。

2) Enc：生成明文 $m\in Z_N$ 对应密文的过程如下

① 通过随机生成h个在0到 $N-1$ 之间的数，生成向量 $C=\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)\in {\mathbb{Z}}_N^h$ ；

② 令 $m_1={\displaystyle \underset{i=1}{\overset{h}{\sum }}{x}_i\cdot {\alpha }_i}$ ；

③ 若 $m_1=m$ 则输出C作为m的密文；

④ 若 $m_1\ne m$ 则随机选取一个 $j\in \left[1,h\right]$ 要求 $x_j\ne 0$，用 ${\alpha }_j+\left(m-m_1\right)x_j^{-1}$ 替换C中 ${\alpha }_j$，其中 $x_j^{-1}\cdot x_j=1$。

那么 $m_2={\displaystyle \underset{i=1}{\overset{h}{\sum }}{x}_i\cdot {{\alpha }^{\prime }}_i}$ 等于m即新的C为有效加密。

3) Dec：给定任意一个密文C和对应的私钥 $K=\left(x_1,x_2,\cdots ,x_h\right)$

① 解密函数 $\Phi \left(x\right)={\displaystyle \underset{i=1}{\overset{h}{\sum }}{x}_i\cdot {\alpha }_i}$ 的结果即为相应明文。

② 若加密次数小于h，则直接应用解密函数。若加密次数不小于h，则对前 $h-1$ 次、h至 $2h-2$ 次…分别应用解密函数。

4) Eval：给定一个希望对密文进行操作的函数和需要处理的密文，将个密文输入到函数中执行同态运算，输出密文c。函数可分解成加法和乘法的组合，对于两个密文c₁和c₂来说，同态加法和同态乘法的表示如下：

同态加法： $c_{add}=\left(c_1+c_2\right)\mathrm{mod}N$ ；同态乘法： $c_{mul}=\left(c_1\cdot c_2\right)\mathrm{mod}N$。

2.1.3. 同态性

将任意两个密文A和B之间的二元关系 ≈ 定义如下： $A\approx B\iff D\left(A\right)=D(\; B\; )$

(加法同态)令 $a=\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)$， $b=\left({\beta }_1,{\beta }_2,\cdots ,{\beta }_h\right)$ 是密文，也即是 ${\displaystyle \underset{i=1}{\overset{h}{\sum }}{x}_i{\alpha }_i=a}$， ${\displaystyle \underset{i=1}{\overset{h}{\sum }}{x}_i{\beta }_i=b}$ ；那么既有如下所得：

$\begin{array}{c}D\left(\epsilon \left(a\right)+\epsilon \left(b\right)\right)=D\left(\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)+\left({\beta }_1,{\beta }_2,\cdots ,{\beta }_h\right)\right)\\ =D\left(\left({\alpha }_1+{\beta }_1\right),\left({\alpha }_2+{\beta }_2\right),\cdots ,\left({\alpha }_h+{\beta }_h\right)\right)\\ =\underset{i=1}{\overset{h}{{\displaystyle \sum }}}{x}_i\left({\alpha }_i+{\beta }_i\right)=\underset{i=1}{\overset{h}{{\displaystyle \sum }}}{x}_i\cdot {\alpha }_i+\underset{i=1}{\overset{h}{{\displaystyle \sum }}}{x}_i\cdot {\beta }_i\\ =a+b=D\left(\epsilon \left(a+b\right)\right)\end{array}$

所以 $\epsilon \left(a\right)+\epsilon \left(b\right)\approx \epsilon \left(a+b\right)$。

(乘法同态)

$\begin{array}{c}E\left(a\right)\times E\left(b\right)=\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)\times \left({\beta }_1,{\beta }_2,\cdots ,{\beta }_h\right)\\ ={\displaystyle \underset{1\le i,j\le h}{\sum }\left({\alpha }_i\cdot {\beta }_j\right)E\left(x_i\cdot x_j\right)}\\ \approx {\displaystyle \underset{1\le i,j\le h}{\sum }E\left({\alpha }_i\cdot {\beta }_j\cdot x_i\cdot x_j\right)}\\ \approx E\left({\displaystyle \underset{1\le i,j\le h}{\sum }\left({\displaystyle \underset{0\le i,j\le N-1}{\sum }{\alpha }_i\cdot {\beta }_j\cdot x_i\cdot x_j}\right)}\right)\end{array}$

$\begin{array}{l}\approx E\left({\displaystyle \underset{1\le i,j\le h}{\sum }{\alpha }_i\cdot x_i\cdot \left({\displaystyle \underset{0\le i,j\le N-1}{\sum }{\beta }_j\cdot x_j}\right)}\right)\\ \approx E\left({\displaystyle \underset{1\le i,j\le h}{\sum }{\alpha }_i\cdot x_i\cdot b}\right)\\ \approx E\left(\left({\displaystyle \underset{1\le i,j\le h}{\sum }{\alpha }_i\cdot x_i}\right)\cdot b\right)\\ =E\left(a\cdot b\right)\end{array}$

2.1.4. 正确性证明

对于任意给定的 $m\in Z_N$ 输出密文 $\epsilon \left(m\right)$ 都有 $D\left(\epsilon \left(m\right)\right)=m$ 成立，通过定义 $\epsilon \left(m\right)$ 可以输出任何密文 $C=\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)\in Z_N^h$ 使得 $\underset{i=1}{\overset{h}{{\displaystyle \sum }}}{x}_i\cdot {\alpha }_i=m$ C被输出也就意味 $\epsilon \left(m\right)=C$ 因此，有

$D\left(\epsilon \left(m\right)\right)=D\left(C\right)=D\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_h\right)=\underset{i=1}{\overset{h}{{\displaystyle \sum }}}{x}_i\cdot {\alpha }_i=m$

2.1.5. 安全性证明

本文的安全性可以规约到的大数分解问题。

大数分解困难性分析：设 $p,q$ 分别是编码在 $\lambda$ 上的素数， $n=pq$。欧拉函数 $\psi \left(n\right)$ 表示不大于n且与n互素的正整数个数。当n是素数，则有 $\psi \left(n\right)=n-1$ 则有 $\psi \left(n\right)=\psi \left(p\right)\psi \left(q\right)=\left(p-1\right)\left(q-1\right)$。

由费马定理，若p是素数，数a与p互素，则 $a^\psi \left(p\right)\equiv 1\left(\mathrm{mod}p\right)$。那么，将N分解为素数p，q乘积的过程就是求解 $a^\psi \left(N\right)\equiv 1\left(\mathrm{mod}N\right)$，我们知道 $\psi \left(n\right)=\left(p-1\right)\left(q-1\right)$，则有 $a^\left(q-1\right)\left(p-1\right)\equiv 1\left(\mathrm{mod}N\right)$。容易看出，上一等式求解规模随p，q的增大成指数级别增加，而目前不能在多项式时间内求解出该问题。例如对十进制五十位的大数进行分解也需要10的11次方年，故而该问题目前仍是困难的。

引理1：任意随机h个密文几乎可以表示为h个独立的方程

证明：概率 $P={\displaystyle \underset{i=1}{\overset{h}{\prod }}\left(1-N^{\left(i-h-1\right)}\right)}$ 式子可知

随着N的增大，P迅速趋近于1。这就意味着人们可以安全地假设任意h给定的密文几乎肯定是独立的。

那么如果在已知P的情况下：

$\{\begin{array}{c}=1-N^{-h}\\ =\left(1-N^{-h}\right)\left(1-N^{1-h}\right)\\ \cdots \\ =\left(1-N^{-h}\right)\left(1-N^{1-h}\right)\cdots \left(1-N^{-1}\right)\end{array}$

那么可以得到h个方程，未知量个数也为h个，则方程有解系统不安全；为了保持安全性，密码系统不能发送超过 $h-1$ 条密文与已知明文。

2.1.6. 性能分析

本文方案采用了大数分解的困难问题，安全级别满足IND-CPA安全。密钥尺寸为 $O\left({\lambda }^h\right)$，因为是无噪声的加密，所以密文膨胀率为0，不需要进行密文清洗，计算复杂度为 $O\left(\lambda \right)$，优于文献 [10] 的计算复杂度。

2.2. 数字签名算法

2.2.1. 作用

1) 验证签名产生者的身份，以及产生签名的日期和时间；

2) 证实被签消息的内容；

3) 由第三方验证，解决争议。

2.2.2. 椭圆曲线离散对数问题ECDSP

本文基于ECDSA (Elliptic Curve Digital Signature Algorithm，椭圆曲线数字签名算法)来实现方案的公开可验证性。椭圆曲线离散对数问题是构造椭圆曲线密码体制的数学基础，即对于椭圆曲线E上两点P、Q，如果已知存在k满足： $Q=kP$，则求解k的问题称为椭圆曲线上的离散对数问题。根据加法法则，计算Q很容易，但给定Q和P，求k就相当困难。ECDSA算法的求解难度是指数级的，因此椭圆曲线算法具有相当高的单位安全强度，具体原理如图1所示。

Figure 1. ECDSA schematic diagram

图1. ECDSA原理图

3. 全同态加密的电子投票方案

基于云端的电子投票的模型如图2所示，认证注册中心CA负责为参与投票的投票人、投票中心和计票中心等实体进行身份认证，为各方实体生成密钥，签发与管理数字证书，确保各实体的真实可靠。投票中心VC负责接受用户端投票人的合法注册，并为投票人分发选票。CA用于存储用户提交的选票以及其它信息。计票中心CC负责验证投票人提交的选票的真实性与合法性，并统计选票结果。

Figure 2. Electronic voting model diagram

图2. 电子投票模型图

3.1. 系统初始化阶段

主要是CA对投票人T、投票中心VC和计票中心CC等实体进行身份认证，这些实体使用ECDSA签名算法生成签名所需的密钥对，公钥为这些实体本身所有，CA用自己的私钥对这些实体的公钥施加数字签名，生成证书并公布出来，其中证书包含这些实体的身份信息以及公钥。

各个实体的密钥对如下：

注册中心： $p{k}_R=Q_R$ ； $s{k}_R=d_R$ ；

投票中心： $p{k}_V=Q_V$ ； $s{k}_V=d_V$ ；

计票中心： $p{k}_S=Q_S$ ； $s{k}_S=d_S$ ；

投票人的： $p{k}_T=Q_T$ ； $s{k}_T=d_T$。

3.2. 投票人注册

投票人需要使用自己的身份材料在注册中心进行注册，注册中心会根据投票人递交的身份信息验证该投票人是否具有投票权以及是否为首次投票，一旦验证通过，则投票中心向该投票人发放与身份信息有关的唯一身份标识 $I{D}_T$ 、唯一投票标识 $B_T$ 、空白选票以及投票公钥 $pk$，并使用自己的私钥对 $I{D}_T\left|\right|B_T$ 进行签名并发送给投票人。将选票编号 $B_T$ 与 $I{D}_T$ 关联，以防止一个 $I{D}_T$ 拥有多张选票。

投票人对收到的签名进行验证，若验证通过，确实为来自注册中心的合法签名，则投票人保存 $\left(I{D}_T\left|\right|B_T\left|\right|Si{g}_v\left(I{D}_T\left|\right|B_T\right)\right)$。同时注册中心需要将 $\left(I{D}_T\left|\right|B_T\left|\right|Si{g}_v\left(I{D}_T\left|\right|B_T\right)\right)$ 发送到公示中心，投票人可以到公示中心查看自己是否已经被公布为合法的投票人。

3.3. 投票阶段

设有n个候选人，投票时投票人选择同意(记为1)或反对(记为0)，若不选视为弃权，则任意一张选票一部分应当包含如下信息： ${\left\{0,1\right\}}^{n\times n}$。投票完成后对选票加密，得到 $Q=\left(C,I{D}_T\left|\right|B_T\left|\right|Si{g}_v\left(I{D}_T\left|\right|B_T\right)\right)$，之后发送给投票中心。

投票中心收到如上信息后，会调用解密算法验证U_id是否合法，若id合法并且在注册中心已被认证，则认为该选票有效。投票中心会把Q分别发送给注册中心和计票系统。

注册中心验证id是否合法。若认证成功则把Q发送给计票中心，同态运算完后返回给注册中心并上传到云端留档，以备将来查验。

3.4. 计票阶段

计票中心收到注册中心发来的密文Q，验证U_id是否合法，若合法则应用同态运算，把计算后的结果发送给注册中心。注册中心在接收消息后验证其合法性，调用同态加密算法的私钥进行解密，并将相应的结果上传到公示板。

3.5. 安全性分析

1) 合法性：在注册时每个投票人都会用自己的身份材料在注册中心进行注册，注册中心在确保投票人身份信息后再进行投票，而数字签名算法确保了数据的可靠性。

匿名性：在投票人通过身份认证信息后，注册中心会发放一个与之身份无关的身份标识，用来隐藏投票人的真实身份信息；其次，在投票过程中采用同态加密对选票进行加密，除了投票人自己，其他任何人都不能获得选票的真实内容，也不能与投票人身份对应。

2) 公正性：通过全同态加密技术，选票信息只有在机票中心通过私钥才可以知晓，其他任何人都无法知道选票信息，因此保证了方案的公正性。

3) 唯一性：在注册阶段，注册中心采用一人一票，保证通过身份认证的投票人有唯一的投票标识。

4) 完备性：首先注册中心对投票人身份信息进行验证，确保身份合法，其次每个人选票有唯一编号，防止重复选票，数字签名对选票内容完整性进行验证，只有全部通过才能被计票中心统计。

5) 可验证性：投票中心会将选票结果公之于众，每位投票人可根据公示信息来确认自己的投票是否被记入。

4. 总结

文中提出了一种基于全同态加密技术的电子投票方案，它综合利用了云计算的分布式特点、强大的计算能力以及安全的数字证书、数字签名、PKI等安全技术，实现了一种安全的电子投票方案。该方案较好地解决了电子投票中的匿名性、完整性和公开可验证性难题，在一定程度上实现了安全、公开、公平和公正的电子投票。不过，相信但随着全同态加密技术研究的深入以及云计算的广泛应用，采用全同态加密技术的电子投票方案将会得到广泛应用。

基金项目

河南科技大学大学生研究训练计划(SRTP)项目(项目编号：2021175)。

NOTES

^*通讯作者。