基于SM2门限盲签名电子选举方案

饶金涛，崔 喆

（1.中国科学院 成都计算机应用研究所，成都 610213；2.中国科学院大学，北京 100049）

0 引言

电子选举作为一个非常重要的科技领域，在维护国计民生和公民的合法权益方面发挥了重要作用，因此它的安全性至关重要。

当前电子选举系统主要分为两大类：

一是基于远程网络通信的电子选举。它的理论基础主要是现代密码学，在投票过程中引入密码技术，根据采用的密码技术模型主要分为盲签名模型、混合网络模型、秘密分享模型和同态加密模型［1］。盲签名模型的电子选举利用盲签名的密码技术实现选票的盲化，实用性较强，满足安全性需求，得到了广泛的应用与研究；混合网络模型的电子选举方案中需要零知识证明，开销较大，在实际的投票活动中难以得到应用；秘密分享模型的电子选举方案需要可信任的秘密分发机构和多个计票机构，投票者、秘密分发机构和计票机构之间的通信复杂度是决定整个选举系统关键核心；同态加密模型的电子选举方案利用同态加密算法加密选票确保实现投票过程的安全性，满足无收据性和可验证性等要求，加密和解密运算的复杂度是影响此类方法的关键［1］。

二是基于抵近物理站站点投票的电子选举。它主要研究设备的稳定性、可靠性与选举系统的关系。所有这些选举方案中使用的密码算法主要是RSA（Rivest-Shamir-Adleman）、ECDSA（Elliptic Curve Digital Signature Algorithm）等国外的密码算法，但近年来国外密码算法漏洞频发，目前最好的解决方案是使用国产密码算法设计选举系统方案，从算法层的实现保证选举系统的自主可控。

1992 年Fujioka 等［1］提出了FOO（Fujioka，Okamoto and Ohta）电子选举协议，首次在电子投票系统中使用了RSA 盲签名算法。基于盲签名的电子投票允许选民盲化投票，因此投票机构可以在不知道选票内容的情况下验证选票。随后出现了基于门限盲签名和基于身份的盲签名两种类型的盲签名。门限盲签名只有当消息由n（n

本文主要研究基于国产密码算法的安全远程网络通信的电子选举系统方案，结合国产的SM2 算法的特点，研究基于Shamir 随机秘密分享（Random Secret Sharing，RSS）、秘密和差、乘积分享和逆的秘密分享（Inversion Secret Sharing，ISS）等秘密分享的方法［2-3］，将门限密码直接应用于SM2 签名算法，实现签名过程中秘密信息的秘密分享。另外针对SM2 门限盲签名算法研究较少的问题，本文方案引入盲化因子实现SM2 盲签名，实现对签名内容的盲化处理，有效保护签名内容。安全分析结果表明，当n>2m（m为多项式最高次数，即是最大的门限数）时，任何2m+1 个参与者都可以产生一个有效的门限盲签名。在此基础上设计了基于SM2门限盲签名的电子选举协议，分析了协议的安全性和性能效率，为国产化电子选举提供基础密码支撑。

1 预备知识

1.1 SM2椭圆曲线公钥密码算法

SM2 密码算法是国产密码算法，包括签名算法、验证签名算法、加解密算法和密钥交换算法。本文主要研究签名算法，使用SM2 算法前需要约定相关参数，包括有限域、椭圆曲线E和基点G=(x0，y0)。签名算法如下：

1）密钥生成r。

步骤1 随机产生一个随机数d作为秘密的私钥dA。

步骤2 计算公钥P=dG。

2）数字签名生成。

步骤1 产生随机数k，计算(x1，y1)=kG。

步骤2 计算r=(e+x1) modN，其中e=H1(M)，M为待签名的消息。

步骤3 计算s=(1+dA)-1(k-r*dA)，输出r、s作为签名结果。

3）数字签名的验证。

步骤1 验证签名者收到r、s和消息m，计算

(x'，y')=sG+(r+s)P

步骤2 计算并判断和是否相等：相等时，签名验证通过；否则，签名验证失效。

1.2 门限密码

1.2.1 Shamir(m，n)秘密分享

Shamir(m，n)秘密分享（Secret Sharing，SS）方案在存在可信任中心的情况下，将秘密信息s分成n份，同时分发给n个参与者，n个参与者中的m+1（m为多项式最高次数）个以上的参与者才能联合恢复秘密信息s。具体如下：

步骤1 可信任中心在域F上构造m阶多项式f(x)=a0+a1x+…+amxm，满足f(0)=a0=s。

步骤2 可信任中心计算f(i)=si，并通过秘密通道将si发送给各参与者(M1，M2，…，Mn)，每个参与者将si作为自己的秘密份额进行保存。

当需要使用秘密信息s时，任意m+1 个参与者形成一个新的恢复集合W，利用保存的秘密份额代入拉格朗日插值公式中直接恢复秘密信息s，这个过程称为m阶分享过程。

1.2.2 基于Shamir随机秘密分享

基于Shamir 的随机秘密分享旨在解决无可信任中心情况下的秘密分享的问题。在基于Shamir 的随机秘密分享中，每个参与者将自己作为可信中心，利用Shamir(m，n)秘密分享方案分享自己的一个秘密信息si，作为自己的秘密份额，从而实现对一个随机数r的秘密分享，随机数的值等于各个参与者秘密分享值的和，即，具体计算如下：

步骤1 每个参与者Mi(1 ≤i≤n)将自己作为可信任中心，选取随机数，并构造共享多项式：

利用Shamir(m，n)秘密分享将通过秘密通道分享给其他n-1 个参与者。

步骤2 第j个参与者收到其他n-1 个参与者发给自己的结果，计算自身的秘密分享的份额此时分享的秘密信息为对应的计算多项式为：

这个过程简称为m阶RSS 过程。

当每个参与者Mi(1 ≤i≤n)选取秘密分享的为0，即所有参与者分享的秘密为0，此时称为联合零秘密分享，简称为m阶ZSS（Zero Secret Sharing）过程。

1.2.3 秘密和差、乘积分享

1）假设参与者Mi得到两个秘密信息s、w的m阶Shamir秘密分享，si=fs(x)、wi=fw(x)，并且s=fs(0)、w=fw(0)，fs(x)和fw(x)是不同的m阶多项式。每个参与者计算ui=si±wi可以得到秘密和差u=s±w的秘密分享份额，此时分享多项式为fu(x)=fs(x)+fw(x)，fu(x)也是m阶多项式。

2）同理假设参与者Mi得到两个秘密信息s、w的m阶Shamir 秘密分享，si=fs(x)、wi=fw(x)，其中s=fs(0)，w=fw(0)，fs(x)和fw(x)是不同的m阶多项式。每个参与者计算vi=si*wi可以得到秘密乘积v=s*w的秘密分享份额，此时分享多项式为fv(x)=fs(x)*fw(x)，fv(x)也是2m阶多项式，并且是不可约多项式，需要对fv(x)进一步进行随机化处理：

步骤1 每个参与者进行2m阶的Shamir 随机秘密分享，Mi的分享份额为αi；

步骤2Mi计算vi=si*wi+αi作为秘密信息v=s*w的秘密分享份额。

此时需要2m+1 个参与者Mi广播它对应的值vi才能恢复出对应的秘密信息v。

1.2.4 逆的秘密分享

文献［3］中说明了逆的秘密分享（ISS），它的基本思想是假设参与者Mi已经分享了一个秘密信息s，对应的份额为si，参与者首先分享一个随机秘密信息λ，然后将计算(λs)-1，从而进一步得到ki=s-1modλ的分享份额。详细方案如下：

步骤1 参与者执行基于Shamir 随机秘密m阶分享随机秘密信息λ，Mi的秘密份额为λi；

步骤2 2m+1 个参与者执行秘密乘积分享λs，并广播自己的秘密份额(λs)i；

步骤3 参与者收到的分享份额(λs)j(1 ≤j≤n)；通过拉格朗日插值公式计算得出λs，同时计算ki=(λs)-1λimodλ得到s-1的秘密分享份额。这个过程称为ISS分享过程。

1.2.5 门限盲签名的安全定义

定义1盲性。给定系统参数，敌手A 能获得签名信息的概率可以忽略。

定义2健壮性。给定系统参数，敌手A 最多可以破坏t个成员的情况下，方案仍可以成功运行。

定义3不可伪造性。给定系统参数，敌手A 最多可以破坏t个成员的情况，敌手A 可以查询p个消息m1，m2，…，mp的签名，敌手A 能产生一个新消息m'的真实门限签名的概率可以忽略。

2 基于SM2门限盲签名算法

2.1 方案构造

对于SM2 签名算法，整个运算过程秘密信息包括随机数k和私钥dA，在签名整个过程中，需要对这两个秘密信息进行保护，同时还需要对签名的信息r进行盲化处理。

2.1.1 密钥产生

从SM2 签名算法可以看出，秘密共享的参数可以变形为(1+dA)-1和随机数k。具体方案如下：密钥产生阶段，主要是SM2 的私钥进行秘密分享，引入可信任中心下的私钥秘密分享，可信任中心随机产生一个随机数作为签名的私钥dA，并计算(1+dA)-1，PA=dAG。按照Shamir 秘密分享的方式执行m阶Shamir 秘密分享，分发给参与者Mi的私钥分量为di，参与者利用di计算对应公钥为Pi=diG，参与者集合为(M1，M2，…，Mn)(n>2m+1)，恢复(1+dA)-1时联合m+1个参与者即可恢复。

2.1.2 签名阶段

签名阶段至少需要2m+1 个参与者。

步骤1 可信中心执行2m阶ZSS 操作，秘密分享份额为δi。

步骤2 可信中心对随机数k执行随机秘密分享，执行m阶RSS，每位参与者分享的秘密份额为ki。

步骤3 每位参与者计算kiG=Ri，用户执行秘密和分享恢复，计算kG=(x1，y1)=R。

步骤4 用户产生盲化因子θ，计算P=θR=(Px，Py)，r=(Px+e)modN，r'=(θ)-1rmodN，并将r'发送给签名者，其中e=H1(M')，M'为待签名的消息。

步骤5 每个参与者Mi计算=di(ki+r')+δi-r'，得到签名s对应的秘密分享的份额

步骤6 至少有2m+1 个参与者广播了它们产生的

步骤7 签名者通过插值公式得到最后的签名值。s'=(1+dA)-1(k+r') -r'，并将它发送给用户。

2.2 算法正确性分析

用户在收到签名值后，首先对它进行脱盲，然后再进行验证，脱盲过程如下：

验证签名正确。

2.3 安全性分析

安全的门限盲签名方案必须满足盲性、健壮性和不可伪造性这3 个性质［4］，文献［4］中进行了定义与分析，本文引用它的引理，结合设计方案并进行证明。具体证明如下：

引理1盲性。用户在得到一个合法的签名后，所有的参与签名的签名者无法得知对应的签名消息。

证明 假设每次签名只有一个参与者的情况，签名者分别和参与者M0和M1交互得到最终的签名值分别为和，其中b∈(0，1)。对于任何一个有效的签名(r'，s')都引入盲化因子θ进行盲化处理，r'=(θ)-1rmodN，θ随机选择，签名者无法得知之间的关系，所以签名者只能以1/2 的概率判定b。根据文献［3］定义的盲签名盲性的安全模型可以得出，当参与者数为n进行门限签名时，签名者只能以1/n的概率判定b，攻击者能成功攻击的概率忽略不计，因此本文方案满足盲性。

引理2健壮性。当n≥2m+1 时，存在中间攻击者，控制了参与运算中m-1 个签名者，签名过程不会被攻击者破坏，依然可以正常进行。

证明 方案中利用秘密分享的方法实现了(1+dA)-1和随机数k两个秘密信息，实现分享的多项式均为m阶多项式，分享签名结果s的多项式是2m阶，恢复签名结果s需要2m+1 签名者才能完成，对于存在m-1 个中间攻击者的行为，需保证n≥3m+1，可以完成签名过程，因此本文方案具有健壮性。

引理3不可伪造性。即使控制了m-1 个签名者，也无法产生有效的签名，即它的门限方案可模拟，具备可模拟的特性，并且攻击者能够成功攻击的概率忽略不计。

证明 ①该方案具有可模拟的特性。

不失一般性，假设攻击者成功控制了前m-1 个参与者{M1，M2，…，Mm-1}，首先证明密钥生成阶段是可以模拟的，模拟器的构建方法同文献［10］，模拟器的输入为公钥P，以及被攻击者控制的m-1 个参与者的私钥份额di(1 ≤i≤m)，定义该前m-1 个签名者为不诚实集合为Q={Qi}(1 ≤i≤m)，其他签名者为诚实集合T={Ti}(m+1 ≤i≤n)，模拟器对集合Q，根据拉格朗日插值公式可以得出：

计算公钥P，同时针对集合T也可以计算公钥P，两者相等，因此在密钥生成阶段可以模拟，模拟器可以模拟攻击者公钥生成的整个视图。

在签名阶段，模拟器的输入为盲化后的消息r'和盲签名后的消息s'，以及被攻击者控制的m-1 个签名者的私钥d的份额di(1 ≤i≤m)，以及随机数k的份额ki(1 ≤i≤m)。对于签名阶段的步骤3，Ri=kiG(1 ≤i≤m)只要有m+1 个参与者就可以恢复出R，由于模拟器得到随机数k的份额ki(1 ≤i≤m)，因此模拟器可以计算针对不诚实者集合Q={Qi}(1 ≤i≤m)计算出R，同时也可以针对诚实的集合T={Ti}(m+1 ≤i≤n)，Ri=kiG(m+1 ≤i≤n)，运用拉格朗日插值计算R，而r'=(θ)-1rmodN，对于不诚实集合Q={Qi}(1 ≤i≤m)有=di(ki+r')+δi-r'，对于诚实集合T={Ti}(m+1 ≤i≤2m)，选取对应的，由(1 ≤i≤2m)，即=s'，可唯一确定一个2m的多项式，从而确定其余的(2m+1 ≤i≤n)，实现模拟器可以模拟攻击者签名消息s'。

②计算攻击成功的概率。

假设攻击者不能访问可信中心的主私钥dA，能够进行q1次可信中心的部分私钥查询，q2次H1的查询，q3次部分盲签名的查询。模拟器随机选择挑战者身份idX，X∈[1，q1]，攻击者与挑战者按照参考文献［2］定义的规则进行以下交互：

a）初始化，挑战者生成系统参数params={E，Fq，G，PA，H1}，其中PA=dAG，H1为SM3 杂凑算法，并将params发给攻击者。

b）可信中心的部分私钥询问。挑战者管理的列表L1为L1=(idi，i)。攻击者每次发起(idj，j)的询问，其中j∈[1，q1]，挑战者收到攻击者的询问后，首先查询(idj，j)是否在列表L1中，如果在，挑战者根据SS 多项式计算f(j)=d'j，RSS 多项式计算将发给攻击者。

c）H1的询问。挑战者管理的列表L2为L2=(ei，ti)。

挑战者收到攻击者关于mi的查询，若mi在列表L2中，则挑战者返回(ei，mi)；若不在，则挑战者随机选择ei∈Fq，发给攻击者，挑战者将它加入列表L2。

d）部分盲签名的询问。当攻击者询问(idi，i，t)时，挑战者首先查询L1和L2，得到相关的私钥分量和ei，再随机选取θ'，计算=(θ'R+ei)modN，r″=(θ')-1modN及r″)+-r″，并将(r″，发给攻击者。

e）伪造签名。若idi≠idX，则伪造失败；若idi=idX，根据分叉引理［6］可以得出，对一个输入的消息t，攻击者可以伪造一个有效的盲签 名进一步得出进而求出可信中心的私钥dA，挑战者利用攻击者的能力成功解决了椭圆曲线上的离散对数问题（Elliptic Curve Discrete Logarithm Problem，ECDLP）的实例。成功伪造签名需要满足以下3 个基本条件，具体如下：

1）事件Ω1表示攻击者没有进行过可信中心的部分私钥的询问，则有：

2）事件Ω2表示攻击者没有进行部分签名查询，则有：

3）事件Ω3表示攻击者伪造签名有效：

因此挑战者利用攻击者的能力以多项式时间不可忽略的概率为ε'解决ECDLP 问题，则有：

挑战者C 以大于等于ε'的概率解决ECDLP 困难问题，与ECDLP 的困难性矛盾，因此可以得出，该方案具有不可伪造性。

2.4 性能比较

为了将本文方案与文献［10-13］方案进行分析对比，为了计算每个运算的时间消耗，本文根据MIRACL 7.0 密码运算库［25］，测试硬件平台为采用Intel i7-8700，处理器主频为3.2 GHz，内存16 GB，操作系统为Windows 10 64 位，关键密码运算计算开销如表1 所示。

表1 主要操作的计算开销Tab.1 Computation overhead of primary operations

对于本文方案，在计算开销方面，可信中心在密钥生成阶段需要执行1 次(1+dA)-1的求逆运算和1 次256 bit 的标量乘运算，用户在分享k时，至少需要执行2m+1 次256 bit的标量乘和m次256 bit 的点加运算。在验证签名阶段进行2 次256 bit 的标量乘运算和1 次256 bit 点加运算，其中哈希函数计算计算量较小，可以忽略不计。因此本方案总的计算量为(2m+4)TP+(m+1)TA+TI（1m为多项式的阶数）。

表2 列出了与其他门限盲签名方案的对比分析（m为多项式的阶数）。由表2 可以看出，本文方案在整个运算过程中无模指数运算，由此可以得出，基于SM2 算法设计的门限盲签名算法在签名阶段和验证签名阶段的总计算开销明显优于其他4 种门限盲签名的方案。由图1 可以看出，随着门限数的增加，其他方案的计算开销的增加速度明显高于本文方案，并且本文方案是基于国产密码算法SM2 提出的，同时适用于大规模选举。

图1 各方案计算开销与最大门限数的关系比较Fig.1 Comparison of relation between computation overhead and maximum threshold number among different schemes

表2 各方案性能比较Tab.2 Performance comparison of different schemes

在通信开销方面，本文以最小的通信开销进行统计分析，本文方案至少需要秘密分享3 个256 bit 的敏感信息，其通信开销至少为m*256*3，同时至少需要产生2m+1 个签名值，每个签名值为512 bit，其通信开销为(2m+1)*512，最后合成的签名结果长度为512 bit，因此总共的通信开销至少为1 792m+1 024 bit。按照同样计算方法，计算得出了文献［10-13］方案的通信开销，具体见表2。另外从图2 中也可以看出，随着门限数的增加，本文方案的通信开销比其他方案的小，并且增长速度较慢。

3 安全电子选举协议方案

基于SM2 门限盲签名算法的电子选举协议方案分为4个部分，分别为生成密钥阶段、注册阶段、投票阶段和计票阶段。

3.1 方案概述

本文方案包括以下几个实体，选民投票终端主要向投票人提供投票服务；注册中心主要是验证选票人身份，同时对选票进行签名；认证中心负责对注册中心及计票中心进行认证，并发放证书；计票中心负责收取XPi=(idi，Mi（)i为第i个选民）选票，验证是否有效，并统计公布结果。具体的方案如图3 所示。

图3 本文方案整体架构Fig.3 Overall architecture of proposed scheme

3.1.1 生成密钥阶段

每个实体均会生成一对密钥对，选民投票终端生成的公私钥对为pkC和skC，注册中心生成的公私钥对为pkR和skR，计票中心生成的公私钥对为pkV和skV。认证中心确认该注册中心和计票中心具有相应资格后，利用私钥对注册中心和计票中心的公钥进行签名，生成并颁布证书，选民可以利用证书中的认证中心的公钥验证实体身份。同时认证中心还针对每个选民Vi产生一对公私钥对di和Pi，其中di为门限盲签名过程中的秘密私钥，Pi为对应的公钥。

3.1.2 注册阶段

1）选民Vi进行注册，由注册中心对选民的身份进行验证，验证完成后，注册中心产生一个与选民身份无关的随机idi，并用注册中心的私钥skR对其进行签名，记为(idi，ri，si)，注册中心将和注册中心的公钥pkR一起发给选民Vi，选民收到后进行验证。

2）选民利用idi生成选票，Yi代表空选票，XPi=(idi，Yi)，计算ei=Hash(XPi)，整个系统利用基于SM2 门限盲签名实现注册中心的签名者、用户本身对选票的门限盲签名，记为，其中di为认证中心通过秘密分享出来的私钥，θ为选民产生的盲化因子。

3.1.3 投票阶段

选民此时得到了一张具有注册中心签名的选票，选民对该选票进行填写，然后利用计票中心的公钥pkV，对填写后的选 票进行加密，结果记为此时选民 将一起发给计票中心。

3.1.4 计票阶段

1）计票中心收到选民发送的选票，利用注册中心的公钥pkR验证选民的idi的签名；

2）利用认证中心下发的公钥Pi验证选民选票的签名

3.2 方案分析

3.2.1 不可伪造性

整个方案中，所有的公钥都是公开的，选民的idi由注册中心进行签名，选民的选票也由注册中心进行签名，同时还需要计票中心的签名。在选票进行注册中心签名时，采用门限盲签名的方案，必须满足n≥2m+1 才可以完成签名，降低了伪造合法选票的可能性。

3.2.2 保密性

本文方案使用门限盲签名对投票内容进行盲化处理，并且利用门限签名保证在投票阶段，选票被盲化因子θ进行盲化处理，无法看到真实内容，同时保护了选民的身份。在投票阶段利用计票中心的公钥pkV对已填写的选票进行加密后再发送，保证了选票内容的安全传送。

3.2.3 合法性

在申请投票时，注册中心对每个投票人的身份进行审核验证，审核验证通过，才发放唯一的选票。用户的公钥和ID是唯一的，在注册阶段，注册中心收到用户的信息，首先核实用户的身份，验证通过后，再发放唯一的ID。选民的每一个ID，只能生成一张选票XPi=(idi，Yi)，保证了选票的唯一性。

3.2.4 鲁棒性

方案采用了门限盲签名的方案，解决了签证人的欺诈行为，必须满足2m+1 个签证人才能完成签名，有效防止签证人的欺诈攻击，对于非法选民来说，是无法伪造注册中心的签名生成的空白的选票。另外如果存在只注册没完成投票过程的选民，选票不会被统计，对整个选举过程不会产生影响。

3.3 实验结果

测试硬件平台依然采用Intel i7-8700，处理器主频为3.2 GHz，内存16 GB，操作系统为Windows 10 64 位测试环境。方案中的签名和加解密算法采用标准的SM2 签名及加解密算法，杂凑算法采用SM3 算法，盲签名算法采用SM2 门限盲签名算法，经过实测，SM3 运算时间为0.009 ms，SM2 签名运算时间为0.915 7 ms，SM2 验证签名时间为1.101 3 ms，SM2 加密运算时间为1.754 3 ms，SM2 解密运算时间为0.953 2 ms。

统计电子选举各个阶段的计算开销，多项式的阶数m=5，参与门限签名实体个数n=11，由于密钥生成阶段可以进行预计算，运算时间只对注册阶段、投票阶段，计票阶段进行分析。在注册阶段进行了1 次SM2 签名运算、1 次SM3 运算、1 次SM2 门限盲签名及验证签名运算；在投票阶段进行了1 次SM2 加密运算；在计票阶段进行了1 次SM2 验证签名运算及1 次SM2 解密运算。注册阶段时间为12.998 6 ms，投票阶段为1.754 3 ms，计票阶段为0.953 2 ms，整个投票过程计算开销为15.706 1 ms。对电子选举各个阶段的通信开销进行统计分析，假设电子选票的数据为1 024 Byte，SM2 加密后数据长度为1 120 Byte，同时由表2可以得出，门限签名阶段的通信开销至少为1 248 Byte，此时总计通信开销为2 368 Byte。

4 结语

随着国产化密码技术的快速发展，国产密码技术在各个行业的应用至关重要。本文提出的基于国产密码SM2 算法门限盲签名的理论算法方案，从理论上进行了分析证明后，提出了实际的应用方案，应用方案具有盲化选票、抵抗伪造选票和防止注册中心签证人欺诈等特点，与同类方案相比，其性能效率具有明显的优势，完成一次投票过程仅需15.706 1 ms，扩展了商用密码算法在电子选举中的应用，后期将考虑如何降低SM2 门限盲签名签名阶段及验证阶段的计算开销。