基于Elgamal强盲签名的区块链电子投票方案研究

邵 清，洪皓洁，李 斌

(上海理工大学 光电信息与计算机工程学院，上海 200093)

1 引 言

投票表决是社会生活中不可缺少的环节，是选举的一种重要手段.过去人们常用的举手表决或纸质投票等，都或多或少存在一些问题，如结果容易被篡改、选举过程不透明等.随着计算机技术的发展，电子投票开始受到人们的关注，它可以降低选举的运行成本，同时满足安全性、隐私性等投票要求.但也存在一些不足之处，如投票者个人信息易泄露、投票过程容易受到攻击、投票数据易丢失等问题.

一个理想的电子投票系统应该具有的重要特性是：

1)合法性：只有经过授权的选民才能投票；

2)完整性：未经检测，不应该修改、伪造或删除选票；

3)可验证性：可能核实的所有选票都应正确计入结果；

4)隐私性：选民的选票不应在任何阶段透露给任何人；

5)匿名性：投票者身份隐藏，任何人不得知晓；

6)公正性：在投票结束前，任何个人或组织不能增加投票者人数或提前披露投票结果；

7)唯一性：每个合法的投票者只能投一次票；

8)稳健性：投票的最终结果不应受到任何因素影响.

电子投票可以应用到社会生活的方方面面，引起了国内外许多研究者的兴趣.经研究，目前主要有4类电子投票方案：基于混合网络的电子投票方案、基于盲签名的电子投票方案、基于秘密分享的电子投票方案和基于全同态加密的电子投票方案.

基于混合网络的电子投票方案，可以抵抗被动攻击，但不能得到混合服务器内部置乱情况.为了解决置乱问题，Furukawa和Sako[1]提出基于混合网络的电子投票方案，在不泄露操作的情况下证明了置乱过程的正确性.Neff[2]提出了可对数据置乱、混淆的实现方法，效率得到提高，并证明了正确性.Luo等人[3]引入盲签名等工具，提出了一种新的无收据电子投票方案.方案满足匿名性要求，但无法满足普遍验证性.Zhao和Liu[4]结合Shamir秘密分享和K-匿名提出一种电子投票方案.同年，Yuan和Li[5]基于Mignotte秘密分享，结合中国剩余定理，提出一种可验证的分布式的电子投票方案，平衡了投票者与计票中心的冲突.但是基于秘密分享的电子投票方案中需要可信任的秘密分发机构和多个计票机构等，这些机构之间的通信复杂度是影响使用的核心要素.Wang等人[6]设计同态密文加法器，结合数字签名技术，提出一种电子投票方案，实现了匿名性和完整性.He等人[7]利用全同态加密，解决电子投票中的身份认证问题.方案支持多个候选人，并利用全同态加密实现了对选票的加密以及求和.但该方案效率不高，难以在实践中应用.在2008年中本聪[8]发表比特币论文后，区块链的关注度大幅提升.区块链的特性很适合应用在投票事件上，与区块链技术结合的电子投票方案解决了许多原有的安全性问题，提高了系统的可追溯性，可以防止恶意攻击或出现欺诈选票等.Jason等人[9]结合盲签名技术和区块链，将盲化后的选票写入交易附加信息，但缺点是仍引入了第三方可信机构.于天娇等人[10]结合RSA算法，提出了基于联盟链的电子投票方案.可链接环签名实现了投票者匿名性.CRUZ等人[11]提出了基于区块链的投票方案，确保安全和不可篡改，但仍需引入可信第三方.

为了解决现有电子投票方案中存在的隐私泄露、不可公开验证等安全性问题以及计票效率问题，本文利用区块链技术，结合基于Elgamal的强盲签名算法和不可链接支付技术，提出了一种新的电子投票方案.方案通过强盲签名算法和哈希函数保证了选票的隐私性、投票者的匿名性，并采用不可链接支付技术使得选票接收者的匿名性也得到了保护，计票效率也得到了有效提高.

2 相关知识

2.1 基于Elgamal签名方程的强盲签名算法

为实现投票者的匿名性，保护选票隐私，本文采用基于Elgamal的强盲签名算法[12]对选票进行签名和加密.在此算法中，签名者不知道消息内容，且请求签名者把已签名的消息公开后，签名者无法追踪所签消息.强盲签名有很强的抗跟踪性，应用到电子投票当中可以有效保护隐私.且强盲签名可以实现对原始消息的鉴别与不可抵赖性，使得投票可验证.

Elgamal签名是一种非确定性的双密钥签名体制，可用于数据加密和数字签名.算法私钥由特定工具生成，为保证私密性仅由使用者保存.在现有算力条件下，方案采用保证算法安全的最小密钥长度，为1024bits.公钥通常由私钥得出，可以公开.在密码体制中，理论上密钥越长，密钥空间越大，则通过穷举计算推测出真实密钥的情况就越难发生，算法安全性也越高.但算法安全性不仅由密钥长度决定，也与现阶段算力和密码体制本身有关.盲签名按盲化程度可分为：弱盲签名、强盲签名和盲参数签名方案.本方案中采用强盲签名算法，用到的签名方程为r=mk+sx[12].

基于Elgamal的强盲签名算法可以抵御伪造给定消息的数字签名的攻击，也可以抵御窃取签名者私钥的攻击，具有较强的安全性.该算法可以打破投票者身份与签名之间的联系，实现投票者匿名性.同时也可以保护所签署消息的具体内容，从而保护选票隐私.

2.2 不可链接支付

采用基于Elgamal的强盲签名算法只是隐藏了投票者的身份信息，为了进一步提高安全性，还需要隐藏选票接收者的信息.为此，方案引入了不可链接支付.

不可链接支付技术来自Nicolas Van Saberhagen的白皮书cryptonote2.0[13].通常，经典的比特币地址一旦公布，就会成为交易的一个明确标识，交易接收者的地址就很容易被“链接”.而不可链接支付打破了输入输出地址之间的关联，允许用户发布单一的地址，并接受无条件的不可链接支付.其主要优势是，每个目标地址的密钥默认都是唯一的.因此就不存在“地址重用”问题，也没有攻击者能确定交易是否被发送到特定地址或是同时链接到两个地址.在电子投票中，如果想隐藏交易接收者的地址，我们可以用不可链接支付技术来实现.不可链接支付的交易模型如图1所示.每个一次性密钥，都由接收者的地址和发送方的随机数计算得到.在交易中，使用一次性密钥使交易地址不容易被“链接”.

图1 不可链接支付交易模型

3 电子投票方案设计

本文提出的电子投票方案结合基于Elgamal的强盲签名算法和不可链接支付技术，通过获得节点访问权后，与区块链上的智能合约进行交互，实现投票过程.

不失一般性，假设一个投票过程需要投票者、接收者和管理者三方共同完成，三方与智能合约进行交互，三方实体交互模型图如图2所示.本方案投票过程分为5个阶段， 分别是：

图2 三方实体交互模型图

系统初始化阶段、注册阶段、选票生成阶段、选票接收阶段和计票阶段.投票方案流程如图3所示.

图3 投票方案流程图

3.1 符号说明

本节给出文中常用的符号说明，如表1所示.

表1 符号说明

3.2 系统架构说明

本文设计的电子投票方案在以太坊(Ethereum)私有区块链上完成，智能合约控制投票协议，完成整个过程.

投票系统由所有用户共同维护和管理，并且共享数据信息.投票的详细信息存储在每个节点中，不需要集中的数据库来存储交易数据，每个节点可以记录每次选举的账本.区块链只允许添加而不允许修改数据，有效地保证了用户可以进行数据认证.区块链中认定最长链为合法链，链的长度会随着投票记录增长.时间戳的存在，使得投票过程是可追溯的.在本方案中，设计了智能合约以实现自动计票，无需第三方参与.智能合约使投票交易自动化，允许双方直接和自动地达成协议，而不需要中间人，提高了可信度.合约对于所有区块链用户都是可见的，因此可以很容易地进行验证.

本方案中，投票由管理者发起，负责每个阶段的开始和结束.在投票开始之前，管理者将在链上部署智能合约.部署后，智能合约将自动完成整个投票过程.整个电子投票方案架构图如图4所示.

图4 基于区块链的电子投票方案架构

3.3 系统初始化

电子投票需要管理者来确保整个过程顺利进行.管理者由所有投票者选举得出，在发起投票前，需设置选举过程中用到的参数并在区块链上公布.所有参与者从公告栏共享信息.理想情况下，我们希望整个投票过程都是通过智能合约来驱动的，确保投票、审核、计票的每一步都是在全体选民的监督下进行.

1)管理者设置项目名称、投票问题及选项等；

2)设置开始和结束时间点，包括注册开始时间、注册结束时间、投票开始时间和投票结束时间；

3)参数设置完成并发布后，投票者将被告知可以开始注册，同时告知智能合约进入下一阶段.

3.4 注册阶段

注册登记由投票者提出申请，根据基于Elgamal的强盲签名算法生成私钥并计算公钥.投票者只有提交公钥和个人信息后，才能成为合法投票者，合法投票者名单将被写入投票者列表.注册阶段应在规定的时间节点前完成，超时系统将不接受任何注册请求.整个注册流程如下：

1)投票参与者提出注册申请；

在初中语文教学中，课本提供的至多只是一幅彩色的画面，产生的视觉效果差，难以激发学生的兴趣。运用现代多媒体技术的声音、形象动感手段，创造与渲染气氛，调动学生的感觉器官和思维器官，使他们耳濡目染、身临其境，进入课文所描述的情境，和作者的思想感情共鸣。这样能给学生更直观的感受，不仅加深了学生对课文内容的理解，而且为课堂教学推波助澜，激发了学生的学习兴趣。

2)投票者生成随机数z∈Zp作为私钥，计算y=gzmodp为公钥；

3)投票者将个人公钥y及身份信息发送给管理者进行注册；

4)管理者审查投票者是否有投票资格，审查通过后向投票者发放身份ID和证书，并将ID发送给智能合约；

5)注册完成后，管理者公布合法投票者总数及投票者名单.

随后，管理者通知智能合约进入选票生成阶段.

3.5 选票生成阶段

在此阶段，投票者需要生成选票，并利用基于Elgamal方程的强盲签名算法，对选票进行加密和签名.一张有效选票需包含正确格式的投票字符串和接收者验证后的签名.

选票生成过程如下：

1)投票者从智能合约中获得投票问题与候选项等信息，生成原始选票m；

2)投票者V结合基于Elgamal的强盲签名算法用私钥对选票进行签名，过程如下：

Step 1.V生成随机数k∈ZP-1，计算r=gk，发送给S；S生成随机数β∈Zp-1，盲化消息m得到m′，即：

m′=βr-β+1mmod(p-1)

(1)

然后把m′发送到V；

Step 2.V对盲化的消息m′签名，计算：

r=m′k+sxmod(p-1)

(2)

得到s，把签名(m′，(r，s))发送给S，签名记为skV(hash(m))；

3)V对消息m计算哈希得到hash(m)，用接收者的公钥对哈希值进行加密，记为pkS(hash(m))，这是构成选票的主要信息；

4)V创建包含加密后的哈希值pkS(hash(m))和签名skV(hash(m))的选票，并通过区块链将选票发送给S.

3.6 选票接收阶段

在选票接收阶段，本文采用不可链接支付技术来隐藏选票接收者S的身份信息，标准投票交易结构如图5所示.通过计算生成一次性不可链接地址，由于使用了哈希函数，根据已公开的P和R，第三方无法逆推得到接收者公钥对(A，B)，所以也无法知道S的身份信息.这就隐藏了交易接收者的地址.

图5 标准投票交易结构

选票接收步骤如下：

Step 1.S选取两个数a，b作为私钥，计算出对应的公钥A=aG和B=bG，并对全网公布这两个公钥；

Step 2.V随机选取正整数q作为私钥，计算一次性公钥P，R：

P=HS(qA)G+B

(3)

R=qG

(4)

Step 3.(P，R)经哈希函数运算后，得到一次性不可链接地址，V将不可链接的一次性地址和投票记录公布到区块链上.S用私钥(a，b)扫描区块链，检查每个经过的投票交易.

若S是交易的接收者，那么aR=aqG=qA，则：

x=Hs(aR)+b

(5)

xG=(Hs(aR)+b)G=Hs(aR)G+bG=Hs(aR)G+B=P

(6)

验证发现符合椭圆曲线加密算法的定义，x即为针对一次性公钥P的私钥，其他人是不可知晓的.此时，S接收到加密选票，且不会暴露自己身份.

S进行逆盲变换，计算：

r′=rβmod(p-1)

(7)

s′=r′r-1smod(p-1)

(8)

得到签名(m，(r′，s′))，但不会知晓消息内容.同时，S用公钥pkV去验证签名的有效性.若签名无效，则忽略；有效则发送回V.

S用私钥sks解密，得到hash(m).哈希函数的存在，使得原始选票内容不可逆推，即S不知道消息m，也就无法知道V的选票投给了谁，从而保证了选票的隐私性.一旦选票被记录在区块链上，V的投票任务就完成了.

之后，S将选票发送给管理者，进入计票阶段.

3.7 计票阶段

到达规定的投票结束时间时，管理者向智能合约发送通知，智能合约将检查所有投票者是否都完成投票.接着，智能合约停止接收投票者的选票，并对接收到的全部选票进行统计，还未投票的投票者视为弃权.计票时，智能合约对于接收到的每一张选票，检查是否包含用于签名该选票的随机数k，如果不存在则接收该选票，存在则拒绝接收.在所有验证之后，包含选票的区块将被添加到区块链中，其他的对等节点则验证并更新他们的链.结果会在链上以广播形式发布，区块链中的所有节点都会同步消息以确保数据准确性.

具体计票过程如下：

1)首先，投票者审查自己的选票是否被记录，若没有，则可以提出申诉，要求智能合约添加自己的选票；

2)智能合约检查投票记录是否已经存在；

3)智能合约将收到的选票密文与投票者列表ID进行对比，将未收到的选票视为弃权票；

4)统计选票，增加相应候选者的票数；

5)智能合约宣布投票结果，并共享给所有节点.

4 本文方案分析

4.1 安全性分析

为了评估所提电子投票方案的安全性，采用STRIDE威胁建模方法，分析系统受到的威胁.威胁建模让我们从攻击者角度去思考问题，更好地去分析每个组件是否可能被篡改、仿冒或是信息泄露等.威胁建模数据流图如图6所示.

图6 投票方案数据流图

分析建模报告可知本文方案面临的威胁主要有欺骗攻击、拒绝服务等.投票者和管理者可能会被攻击者欺骗，在恶意节点上进行投票.这种情况需要恶意节点拥有超过全网51%的算力，可能性非常小.拒绝服务是指消耗资源或者服务、功能不可用.分布式的账本数据库，保证了即使某一节点受到攻击，整个系统数据仍能更新，不会丢失，但这带来的资源消耗问题也是值得重视的.服务不可用情况一般是负载均衡没有做好，本方案属于小规模投票，不存在访问压力过大情况，一般不会出现.区块链的去中心化有效保障了节点安全，但我们需要足够多的节点来保护网络，否则也会增加51%的攻击风险.本方案的设计是为了实现加密传输选票并能自动正确计票，从这一角度来看，安全性还是可以得到保证的.

下面对方案的其他属性进行简要分析：

1)合法性：结合了基于Elgamal的强盲签名算法的投票方案，利用盲签名的不可伪造性，任何非法人员都无法获得身份授权，有效维护了投票者身份的合法性.

2)完整性：由于区块链不可篡改的特性，在所有选票被发送到智能合约后，任何人都不能对其进行修改和删除，并且这一过程是所有节点共同监督的.由基于Elgamal的强盲签名算法可知，投票者的私钥不泄露情况下，他人无法进行冒充投票.

3)可验证性：本方案提供了公开验证投票过程的机会，根据智能合约公布的总票数份额，以及给投票者发送的签名认证，对等节点或任何人都可以监视正在发生的投票活动，每位投票者都可以查看自己的选票是否被统计.

4)隐私性：强盲签名和哈希函数的存在使得任何人都不知道原始消息m，保护了选票隐私，即保护了候选者隐私.采用一次性不可链接地址，使任何人不可逆推公钥对(A，B)，保护了选票接收者的隐私.

5)匿名性：投票者在投票过程中，利用接收者公钥对选票进行加密，利用自身私钥对选票签名，除了投票者本人，任何人都不能将投票者的身份信息和签名、加密选票间建立联系，即实现了投票者匿名.

6)公正性：在到达规定的投票结束时间时，智能合约开始自动执行计票，无需第三方机构参与，并只对有效选票进行统计，投票结果无法被任何人或机构知道，满足了公正性.

7)唯一性：注册阶段，每个投票者会生成一个唯一的随机数作为标识，在后续投票中，如果重复计算了随机数，就认为该投票者重复投票，是无效的.基于Elgamal的强盲签名算法确保了一个投票者只能签名一次，只能进行一次投票，满足了唯一性要求.

8)稳健性：整个计票过程由智能合约完成，投票时间截止后，将不再接收选票.选举结果在公布在公告栏，任何人都无法修改投票最终结果.区块链共识机制使得所有对等节点同步消息，且投票不可篡改，投票过程满足稳健性要求.

4.2 对比分析

本节将该方案与文献[14]和文献[15]提出的方案进行定性对比分析，结果如表2所示.

表2 不同电子投票方案对比分析

文献[14]利用分布式Elgamal算法对已有的安全电子投票方案进行了改进，有效隐藏了传输矩阵中的数据，使得串谋者无法得到传数矩阵中的具体数值，有效保护了选票隐私，实现完全保密性.方案的不足是仍要求第三方计票机构绝对.文献[15]提出了基于区块链的电子投票方案，方案中利用了分布式Elgamal加密体制和零知识证明协议，保证了选票内容的安全传输，保证了投票者及选票内容的合法性，有效防止重复投票.但方案可能会泄漏候选者的隐私，也没有考虑到大规模投票场景.和上述两种电子投票方案对比，本文方案取消了传统方案中的计票第三方，满足了区块链去中心化的特性，避免了计票机构的欺骗行为，保护了投票者和候选者的隐私.

5 性能分析

本方案的性能分析实验在本地以太坊私有区块链网络上进行，系统为ubuntu 18.04.

为了验证方案的正确性与有效性，通过调试不同数量的投票者，在不同数量的候选者情况下，对计票时间进行统计，结果如图7所示.可以看出，计票时间与投票者数量基本呈线性相关，即随着投票者数量的增多，计票时间也相应地增加，候选者数量的不同对计票耗时无较大影响，因此本文方案能够满足基本投票场景要求.

图7 不同投票者数量下计票时间对比

为了验证计票效率，将本文方案与文献[14]和文献[15]方案在相同数量候选者、不同数量投票者情况下所用计票时间进行对比，结果如图8所示.图8表明随着投票者数量增多，方案所用时间都相应地增多，但时间差却逐渐增大.本文方案计票耗时相较于文献[14]和文献[15]来说，整体较少，计票效率有一定提高.

图8 不同电子投票方案计票时间对比

为了验证方案的匿名性，以条件熵[16]作为评价指标，来表示不确定度.由于候选者的支持者肯定会将票投给该候选者，这里指的是保持中立的投票者的匿名性.将投票者匿名性定义为投票者选择的不确定性，这样就可以用条件熵来量化匿名性.

简化投票模型，假定只有两个候选者P1、P2，得票数分别为p1、p2，保持中立的投票者数量为d，则三者之和即为投票者总数.下面给出当投票者组成为P1：P2：d=1：1：2时，条件熵与投票者数量的关系.H(X|Y)表示投票结果只公布胜出者，不公布各候选者具体得票数情况下的条件熵；H(X|Z)表示宣布各候选者具体得票数情况下的条件熵.实验结果如图9所示.

图9 投票者匿名性与投票者数量的关系

计票结果未公布时，投票者完全匿名，即条件熵为1.由图9可以看出，公布计票结果，使得投票者的匿名性降低.随着投票者数量的增加，即投票规模越大，投票者匿名性越高.H(X|Y)与H(X|Z)始终存在差值，即在公布所有候选者得票数情况下，投票者身份更易泄漏，匿名性更低，这也是符合常理的.在电子投票中，为了保证投票者匿名性，有时可以选择不公布各候选者的得票数，公布结果的方式可以根据实际情况适当调整.

6 结束语

本文通过分析区块链的底层密码学原理，结合基于Elgamal的强盲签名算法和不可链接支付技术，提出了一种可公开验证的匿名电子投票方案.智能合约的存在，允许在没有可信第三方的基础上完成选票的统计，提高了计票效率，并能对欺骗行为进行检测.区块链技术确保各节点共同维护账本信息，降低了传统中心机构对数据的绝对控制权，同时可以避免因中心机构故障导致的数据丢失问题.方案满足电子投票的基本安全性需求，实现了较好的匿名性，在计票效率上有一定程度的提高，符合实际投票场景需求.