门限SM2签名方案

唐张颖，王志伟，2

(1.南京邮电大学计算机学院、软件学院、网络空间安全学院，江苏 南京 210023 2.南京邮电大学江苏省大数据安全与智能处理重点实验室，江苏 南京 210023)

随着全球数字化进程的深入推进，区块链产业也在飞速发展。这期间，区块链钱包也由单资产钱包、单链钱包发展为多链多资产钱包，从单一的转账收款钱包发展为区块链生态服务平台。比特币以及其他加密货币系统中广泛使用了ECDSA签名算法，通过验证签名来保证信息的真实性［1］，确保交易过程顺利执行。SM2签名算法［2］作为我国自主研发的公钥密码算法，加入了用户特异性等信息且椭圆曲线参数需要利用算法产生，使SM2算法相较于ECDSA算法安全性有所提升。为了保证用户的数字资产，使用更安全的签名算法是有必要的。

钱包系统中私钥一旦丢失或泄露，用户的资产安全将受到严重威胁。现实生活中通过借助可信第三方来对应用户身份和密钥，以此保护用户资产。但在区块链系统中，借助可信第三方生成私钥［3］的方式会导致出现非法者恶意攻击可信第三方、获取用户的个人隐私、发送错误信息等违法行为。为了解决这个问题，国内外学者提出了门限签名［4］的思想，签名私钥存储于多个参与方手中，只有当指定人数的参与方同意时才可以生成特定消息下的签名，有效地实现了权力的分配。门限签名的思想能够有效地抵抗恶意行为，保护用户资产，因此，构造一个门限SM2签名方案是有意义的。

1 相关工作

门限思想最早由Shamir和Blakley分别独立提出，Desmedt和 Frankel［5-6］引入了门限密码的概念，彻底打开了门限密码研究的大门。门限签名是门限秘密共享技术和数字签名的一种结合，由至少门限值数量的参与方合作运行，任意少于门限数量的参与方无法合谋进行签名。

Gennaro等［7］提出的门限签名方案中，需要 n方参与者集合中不少于2n／3的参与者合作进行签名，但很容易受到敌手控制n／3或者更多参与者的攻击。 改进的 （t，n）门限 ECDSA 方案［8］需要事先选择一个包含t位诚实参与者的签名小组，然而只要小组内有一方崩溃或者某一方是恶意的敌手，签名就会失败，这可能会演变为对手控制一方或少数参与者来阻止系统签名。Mackenzie等［9］提出特定两方协议，但该协议严重依赖于低效的零知识证明，因此产生的协议没有实际意义。

尚铭等［19］针对国产SM2签名算法提出了SM2椭圆曲线门限密码算法，私钥信息被分享给独立的多个参与者，但是该算法中总成员数n必须大于等于2t＋ 1，不适用（2，3）等区块链签名。 Zhang 等［20］提出的SM2签名算法的两方协同方案也使用了Paillier同态加密技术，同样需要复杂的范围证明。

为了解决上述问题，本文基于同态加密CL方案，提出一种基于SM2签名算法的门限签名方案，方案的贡献如下：

（1）门限方案仅限制签名人数n≥t＋1，即使签名者集合中恶意者占多数，方案仍能提供安全有效的签名。

（2）多方参与者利用CL同态加密方案生成各自的签名，同时对CL密文提供相应的零知识证明，保证密文格式正确。

（3）文中采用了针对离散对数关系的零知识证明算法ZKPoRepS，算法通过使用额外一轮挑战消除阶已知的群F＾上的元素，借助通用群模型证明了HSM群上离散对数关系的安全性；额外的挑战使证明轮数降为一次，相对于同类方案［4］中使用的零知识证明算法，通信开销和计算速度都得到提升。

2 预备知识

2.1 SM2签名方案

签名者首先输入系统公共参数p、q、E、P。 其中，p是大素数，E是定义在有限域Fp上的椭圆曲线，G是E上的q阶基点。签名方案包括以下算法：

（1）密钥生成算法。签名者选择随机的私钥d，d∈ ［1，q-1］，计算公钥 P ＝ dG。

（3）验证算法。验证方收到签名者发来的消息m 和签名 （r′，s′） 后，首先判断 r′，s′∈ ［1，q-1］，r′＋s′≠q是否成立，若不成立则验证失败；计算t＝（r′＋ s′）， 若 t＝ 0， 验证失败；计算 （x′1，y′1） ＝ s′G ＋tP； 最后计算 R ＝ （e′＋ x′1）mod q； 若 R ＝ r′， 验证通过，否则验证失败。

2.2 基于HSM群的CL加密方案

根据文献［14］提出的群生成算法构造HSM群，输入安全参数1λ和素数p，GGenHSM算法输出公共参数。 其中，有限交换群的阶为·q，在多项式时间内可以判断某元素是否在群上。是生成元的阶。是上阶为q的循环子群，由生成，多项式时间内可以通过 Slove（·）［4］算法解决中的离散对数问题。 G是中阶为q·s的循环子群，由g生成，s划分了。Gq是群G上阶为s的子群，由gq生成。方案中设gq由经过幂运算得到，具有随机性。通过构造⊂ G，有成立。 CL 加密方案包括以下算法：

（2）加密算法。输入公钥pk和消息m，选择随机数 ρ， 计算密文 （C1，C2）， 其中，

（3）解密算法。输入私钥sk和密文（C1，C2），计算， 使用 Slove（·）算法解决上的离散对数问题，返回明文m←Slove（M）。

2.3 数学假设

对于门限SM2签名方案，依赖以下困难假设：（1） HSM 假设。gq由经过幂运算得到且具有随机性，因此区分群G上的某元素是否在子群Gq上是困难的。设群由生成，整数上的分布D（Dq） 距离群 G（） 上的均匀分布的距 离少于 2-λ， 概率为敌手A的优势，若对于所有概率时间算法，A的优势可以忽略，称HSM问题在G上是困难的。

3 安全模型与定义

本文采用基于游戏的安全定义［4］：选择明文攻击下的门限不可伪造性（tu-cma）。通过构造模拟协议，利用与敌手的交互，将安全性归约到原始签名方案的安全假设。

3.1 安全模型

假设存在一个多项式时间算法A破坏了门限SM2方案的密钥生成过程和签名过程，伪造者F可以利用A算法来打破标准SM2签名算法的不可伪造性。模型中F模拟A的环境，使A无法区分自己处于真实环境还是正在与F交互。若A摧毁了某参与方 ｛Pj｝j＞1，F 模拟参与者 Pi， 算法过程中 F 的输出和A与诚实Pi交互得到的输出难以区分。F拥有SM2签名算法的公钥P，可以向签名预言机询问选择的消息，询问之后必须输出伪造的消息签名σ。

3.2 安全性定义

数字签名方案所需的标准安全概念是选择明文攻击下的存在性不可伪造。针对此标准，传统签名方案的安全性已经得到了证明［21］。

（1）存在性不可伪造（eu-cma）。假设一个数字签名方案S包含产生密钥、生成签名和验证3个过程。某概率多项式时间算法A输入公钥vk后可以访问签名算法的预言机Sign（sk，·），此预言机可以自适应地对其选择的消息请求签名。对于算法A，数字签名方案S是存在性不可伪造的。设M为询问的消息集合，A对不属于M的消息m产生合理签名的概率是关于安全参数λ的函数，可以忽略不计。

（2）门限签名不可伪造（tu-cma）。假设一个（t，n）门限数字签名方案IS包含产生密钥、生成签名和验证3个过程，方案中存在一个最多攻击t个参与者的概率多项式时间算法A，可以看到产生密钥、自适应地选择消息和对消息签名的过程。对于算法A，门限数字签名方案IS是不可伪造的。A对不属于M的消息m产生合理签名的概率是关于安全参数λ的函数，可以忽略不计。

4 门限SM2签名方案

门限SM2签名方案包含3个阶段：生成CL方案公共参数、产生密钥、生成签名。算法表1、2、3、4直观地展现了各阶段的交互过程，除表4的阶段2由参与方两两成对完成，其他阶段每个参与方执行相同的操作，因此文中仅描述某参与方Pi执行的操作，当Pi广播某些信息时，也隐式地从其他参与方 ｛Pj｝j≠i接收到这些信息。表中点对点通信用单箭头表示，广播用双箭头表示。

4.1 生成CL方案公共参数

4.1.1 生成随机公共素数

（1）各参与方Pi首先选择随机数ri，计算ri的承诺 （gci，gdi）［22-23］，向其他成员广播gci。

（2） 接着，Pi收到其余方 ｛Pj｝j≠i的承诺｛gcj｝j≠i后，广播gdi； 待收到 ｛Pj｝j≠i广播的gdj后，Pi执行ri← Open（gci，gdi） 打开承诺。

（3） 最后，Pi算出公共输出

4.1.2 生成公共参数gq

（1） 得到 （，q） 后，Pi首先通过文献［14］中的方法算出生成元。

（2） 然后，Pi选择随机的ti， 并计算； 接着，Pi计算gi的承诺并广播。

（3）待Pi揭开其他参与方的承诺后，计算关于ti的零知识证明 ZKPoRepS［24］（如表1所示，其中B是安全参数），以此向其他参与方证明自己知道ti。一旦证明验证失败，中止方案。

表1 ZKPoRepS零知识证明

表2 生成CL方案的参数

4.2 产生密钥

在产生密钥的算法中，对于n方参与者，设定门限值t，其中n＞t。 整个流程如表3所示。

表3 生成签名方案公私钥

（1）Pi首先选择随机的ui∈Z／qZ，计算uiG的承诺，并生成CL加密方案的公私钥（ski，pki）；之后广播自己的公钥和对uiG的承诺。

（3）然后，Pi对秘密值ui执行基于Shamir秘密共享［25］的 Feldman-Vss 算法［26］，执行该算法得到的结果di是签名私钥d的 （t，n）Shamir秘密共享。

（4） 最后，Pi使用 Schnorr［27］提供的零知识证明ZKPoK，向其他参与方证明自己知道di。

4.3 生成签名

签名的整个过程如表4所示。定义S⊆［n］为对消息m签名的参与者集合，设｜S｜＝t时Pi可以使用适当的拉格朗日系数将私钥d的（t，n）份额｛di｝i∈［n］转换为d的 （t，t） 份额 ｛wi｝i∈S， 也可以将（1＋d）-1的 （t，n） 份 额 转 换 为 （t，t） 份 额｛vi｝i∈S。

表4 签名过程

4.3.1 对随机份额加密

5 安全性

本文所设计的门限SM2签名方案的安全性是基于原始SM2签名方案的可证明安全性。本节主要证明了方案中生成签名阶段的安全性，生成参数阶段和产生密钥阶段的安全性可以通过引用文献［4］来证明。签名过程中所有参与方都执行了相同的操作，因此模拟器F只需要模拟其中某一位参与方P1。

5.1 模拟签名的生成

在密钥生成阶段的模拟中，模拟器F获得了其他参与者的秘密值 ｛wj｝j∈S，j≠1、 ｛vj｝j∈S，j≠1和公钥｛p kj｝j∈S。 在模拟签名阶段，F输入消息 m 后，需要模拟与敌手A交互的过程。模拟过程中，一旦A拒绝打开任何承诺，或者零知识证明失败，或者签名（r，s）未通过验证，F都会中止操作。

5.1.1 对随机份额加密

（2） 接着，F 发布密文 ck1，c＾v1对应的 ZKAoK 零知识证明 π1，π′1，并计算 Γ1＝ γ1G 的承诺 （sc1，sd1）。

（3）当F接收到A发送的密文、承诺和零知识证明 （ckj，cvj，scj，πj，π′j） 后， F 广播 （ck1，c＾v1，sc1，π1，π ′1） 。

5.1.2 计算中间变量 （ρi，σi，δi）

（a）F向SM2签名预言机询问m的签名 （r，s），计算R ＝s（G ＋P） ＋rP ＋m∈Z／qZ，r＝Rx＋e。

（b）接着，F对A重放（1）的步骤，在不被A发现的前提下模糊P1对Γ1的承诺。

（c） F 从 A 接收到 ｛s dj｝j∈S，j≠1后打开承诺，获

5.2 证明总结

F可以判断自己是否处于半正确的执行过程，因此F能及时调整模拟，令A无法察觉，签名阶段所有的模拟都和真实协议的执行不可区分。F从自己的SM2挑战那里得到系统公钥，当A破坏了门限SM2方案中的t位参与方时，F把最终生成的签名作为自己的伪造，从而打破SM2签名算法的存在性不可伪造。

假设SM2签名算法是存在性不可伪造的，数学假设成立，CL加密方案是选择明文下不可区分的，则门限SM2签名方案是存在性不可伪造的。

6 效率

在本文中，设计实验对门限SM2签名方案和门限ECDSA签名方案［4］的效率进行了对比分析，从产生密钥、生成签名的计算量进行了评估。令签名者集合记为n，门限值记为t，群F＾上的幂运算相对于类群中的幂运算几乎可以忽略，因此文中省略了群F＾上的计算次数，仅列出了类群中的幂运算。由表5可知，本方案在产生密钥阶段的零知识证明计算量减少，这是因为文献［4］构造的零知识证明算法对所证明的离散对数关系做了修改，之后使用最低公共多重（lcm）技巧来证明修改后的离散对数关系，协议需要重复执行多轮来保证安全性。本文方案采用的紧凑型零知识证明算法ZKPoKRepS使用额外一轮挑战来消除群F＾上的元素，借助通用群模型，证明轮数仅需要一次，使该阶段的计算速度相对于文献［4］提升了约46%。

表5 门限SM2和门限ECDSA方案计算量对比

在通信开销方面，如表6所示，本方案由于采用ZKPoKRepS算法，产生密钥阶段的通信开销也降低了60%以上；生成签名阶段本方案的通信开销要略高于门限ECDSA方案，这是因为SM2签名算法自身非线性的特征，参与方计算密文和同态加密，以及零知识证明都需要更多次幂运算，使签名者之间交互产生的通信开销相应增加。

表6 不同安全级别下通信开销对比

为了显示不同签名人数的情况，选取（t，n）分别为（1，3），（2，4），（2，5）来分析不同签名人数和门限值的通信开销。随着签名人数的增加，通信开销也在线性增长，由图1可以更直观地发现本方案在密钥阶段的通信开销上得到了提升。

图1 128比特安全下（t，n）门限签名方案

综合考虑，虽然本文方案在签名阶段通信开销要略大于门限ECDSA方案，但是在密钥阶段要远远小于后者，并且ECDSA方案对消息不做任何处理，本SM2签名方案需要对消息作预处理，处理后消息加入了用户特异性等信息，使本方案的安全性也有明显提升。

7 结束语

本文基于门限签名的思想设计了门限SM2签名方案，允许在签名群体中恶意者占多数的情况下保证签名的顺利进行。门限SM2签名方案基于HSM困难问题，利用CL算法传输密文，签名过程由各方合作完成，实现了权利的分配。文中采用基于模拟的证明方法，通过构造模拟协议，利用与敌手的交互将安全性归约到原始签名方案的安全性。最后，本文针对通信量和计算量与Castagnos等［4］的门限ECDSA方案进行对比，在产生密钥阶段明显优于门限ECDSA方案。由于SM2算法自身非线性的特征，在签名过程中需要额外传输乘法份额的密文等信息，在签名阶段需要更多的通信开销。