基于SM2数字签名算法的适配器签名方案

在过去几年中，区块链技术受到了学术界、产业界以及政府部门的高度关注，它能够在互不信任的分布式系统中实现安全支付、数据交易甚至更为普适的计算模式.它的核心是通过一个去中心化的共识协议，每个参与节点共同建立并维护一个存储所有交易的分布式账本.以比特币、以太坊为代表的数字货币均依赖于区块链系统，并基于区块链的脚本语言提供丰富的交易方式.虽然区块链上每笔交易记录具有公开可验证性，但它的交易吞吐量扩展问题也非常明显[1].例如，比特币每秒大约可以完成10笔交易，比信用卡网络低3个数量级[2].

为解决区块链交易扩容问题，研究人员提出了支付通道(payment channels)[3]的概念，即在不破坏交易安全性的前提下支持任意数量的线下交易，且仅将最终的交易状态上链，从而完成交易.比特币中的闪电网络(Lightning Network)[4]和以太坊中的雷电网络(Raiden Network)[5]均采用支付通道技术实现.然而，构建支付通道的一个关键点是如何撤销旧的交易状态.为此，以闪电网络为代表的支付通道采用了惩罚机制来让受骗方获取所有的货币(包括不诚实交易方的货币)[6].由于矿工收取的交易费用与每笔交易中包含的脚本大小以及矿工验证所需的计算量成正比，故需要尽可能的降低链上交易规模.一种有效的途径是在链下管理一些交易逻辑，即将交易逻辑编码为发送方和接收方之间的点对点协议，而不是直接在交易脚本中进行逻辑编码.由此出发，Polestra引入了无脚本脚本(scriptless scripts)的概念[7]，后来将其形式化为适配器签名(adaptor signature, AS)[8-9].

适配器签名方案是标准数字签名的一种扩展形式，它可以创建一个隐含困难关系(例如离散对数)状态的“预签名”，并通过困难关系证据将该预签名可以转换为一个完整签名，且转换得到的完整签名可以由一个标准签名方案的验证算法验证有效性.直观地说，适配器签名应具备2个属性：1)只有知道困难关系证据的用户才能够将预签名转变为完整签名；2)任何用户可以通过预签名和完整签名提取困难关系证据.基于这2个性质，适配器签名方案能够在区块链中提供很好的原子交换性质，并已在实践中被证明应用非常广泛.例如，它可以构建链下支付应用程序，包括通用支付通道[8]、支付通道网络[10]、支付通道集线器[11]等，也可被实际的区块链协议采用，例如闪电网络、雷电网络等.

在本文中，我们以SM2数字签名算法为基础，构造了一个新的适配器签名方案，记为SM2-AS.该方案能够有效地衔接SM2签名方案的密钥生成、签名生成和签名验证算法.我们在随机预言模型下证明了SM2-AS方案是安全的，即满足预签名正确性、预签名可适配性、选择明文攻击下的存在不可伪造性和证据可提取性.理论分析和实验测试表明，SM2-AS方案的性能虽然弱于Schnorr适配器签名方案，但与ECDSA适配器签名方案相当.

1 相关工作

在Polestra提出无脚本脚本[7]的概念后，Aumayr等人[8]设计了基于Schnorr签名和ECDSA签名的适配器签名方案，并将其用于通用支付通道的构建.Malavolta等人[10]基于单向同态函数构建了适配器签名方案.同年，Moreno-Sanchez等人[12]针对门罗币中的可链接环签名方案构造了一个新的适配器签名，以改进门罗币的交易脚本逻辑.此外，文献[10-11]分别给出了将适配器签名方案用于构建支付通道网络和支付通道集线器的方法.

随着量子计算威胁日益增强，以太坊和零币均开展了向抗量子攻击的密码学原语迁移的计划.为此，Esgin等人[13-14]设计了第1个基于标准格的适配器签名方案LAS.但LAS在正确性、通信开销和隐私性方面存在一些问题，即仅具备弱预签名可适配性、较大的预签名尺寸.随后，Tairi等人[14]设计了第1个基于同源的适配器签名方案IAS，该方案是基于CSI-Fish签名方案扩展而成的.另外，Qin等人[15]给出了第1个基于身份鉴别协议的适配器签名通用构造方法，并验证该方法可支持离散对数形式、RSA形式、格基形式的鉴别协议.并且，Qin等人[15]给出了适配器盲签名和可链接适配器环签名的实例.

2 预备知识

本节我们给出本文的符号约定，并描述签名算法、困难关系和非交互式零知识证明的概念.

2.1 符号约定

本文中，我们用表示整数集合{1,2,…,n-1}，x←$表示从集合均匀随机抽取一个整数.{0,1}*表示任意长度的比特串.是一个阶为q的椭圆曲线点群，G是的生成元，其群运算法则用+表示，标量运算用k·G表示(k∈为标量).λ表示系统安全参数，ε(·)表示可忽略函数.

2.2 签名算法

一般而言，传统的数字签名方案Σ=(Gen,Sign,Vrfy)包含3个算法：密钥生成算法Gen、签名生成算法Sign和签名验证算法Vrfy.各算法的功能描述为：

1) Gen(1λ).该算法以系统安全参数λ为输入，输出一对私钥sk和公钥pk.

2) Signsk(m).该算法以私钥sk和消息m∈{0,1}*为输入，输出一个签名值σ.

3) Vrfypk(m;σ).该算法以公钥pk、消息m和签名值σ为输入，输出验证结果b∈{0,1}.若b=1，则表示签名有效；否则，签名无效.

从安全性角度而言，若一个数字签名方案是安全的，则必须满足2个性质：

1) 正确性.即对任意的消息m和密钥对(sk,pk)，有Vrfypk(m;Signsk(m))=1.

2) 选择明文攻击下的强存在不可伪造性.即对于任意的公钥pk，敌手即使可以访问pk对应的签名预言机，也无法伪造任意消息m的一个新的合法签名.

2.3 困难关系

令Π是一种二元关系，LΠ是描述这种关系的语言，即LΠ{Y|∃y s.t.(Y,y)∈Π}.若3个性质成立，则称Π是一种困难关系：

1) 存在一个概率多项式时间算法能够产生一组实例，记为(Y,y)←GenΠ(1λ).

2) 存在一个确定性的多项式时间算法能够验证给定的(Y,y)是否属于关系Π.

3) 对于任意的多项式时间敌手，通过Y计算得到y的概率是可忽略的.

一般称Y为困难关系状态，y为困难关系证据.

2.4 非交互式零知识证明

对于某种给定的困难关系，当证据持有者需要向他人证明其所拥有的证据且不泄露证据的任何信息时，就需要用到零知识证明.非交互式零知识证明(NIZK)包括2个算法：证明生成算法P和证明验证算法V.其中，证明生成算法P(Y,y)以状态Y和证据y为输入，产生一个有效的证明π；证明验证算法V(Y,π)以状态Y和证明π为输入，输出一个比特b∈{0,1}表示该证明是否有效.若b=1，则表示证明有效；否则，表示证明无效.在本方案中，所使用的零知识证明协议需要满足3个性质：

1) 完备性(completeness).即对任意的(Y,y)∈Π，均有V(Y,P(Y,y))=1.

2) 零知识性(zero-knowledge).即存在一个多项式时间的模拟器S，能够模拟产生任意困难关系实例(Y,y)∈Π的一个证明π.

3) 在线提取器(online extractor).存在一个多项式时间的在线提取器K能够访问随机预言机的询问列表，并能够提取任意状态Y及其证明π中的证据y.

3 适配器签名基本概念

本节我们主要介绍适配器签名的系统模型和安全模型.

3.1 系统模型

本质上，适配器签名是一种两步式的签名算法：拥有私钥的签名者对一个消息和一个秘密值的承诺进行预签名，拥有秘密值的适配者可将预签名值适配为完整的签名值.具体而言，适配者首先产生一个困难关系(Y,y)←GenΠ(1λ)并公开状态Y；签名者对给定的消息m和状态Y使用私钥sk进行预签名，并将预签名值发送给适配者；适配者对于给定的预签名值使用秘密值y进行适配，得到完整的签名值σ.此外，任何人获取到σ和时，可提取秘密值y.适配器签名方案的形式化定义为：

定义1. 适配器签名.对于一个数字签名方案Σ=(Gen,Sign,Vrfy)和一个困难关系Π，适配器签名方案ΞΣ,Π=(pSign,Adapt,pVrfy,Ext)包含4个算法：预签名生成算法pSign、预签名验证算法pVrfy、适配算法Adapt和提取算法Ext.各算法的功能描述为：

1) pSignsk(m,Y).该预签名生成算法以一个私钥sk、一个消息m和一个困难问题状态Y为输入，输出一个预签名值

该预签名验证算法以一个公钥pk、一个消息m、一个困难问题状态Y和一个预签名值为输入，输出验证结果b∈{0,1}.若b=1，则表示签名有效；否则，签名无效.

该适配算法以一个预签名值和一个困难问题证据y为输入，输出一个签名值σ.

该提取算法以一个签名值σ、一个预签名值和一个困难问题状态Y为输入，输出满足(Y,y)∈Π的困难问题证据y或者失败符号⊥.

3.2 安全模型

相比普通数字签名方案而言，适配器签名方案需要满足5个定义性质.

定义1. 预签名正确性(pre-signature corr-ectness).一个适配器签名方案是预签名正确的，若对于任意消息m和任意困难问题实例Y，均有:

可见，定义1中隐含了数字签名方案Σ的正确性，并对预签名过程和证据提取过程进行正确性约束.

定义2. 预签名可适配性(pre-signature ada-ptability).对任意的关于公钥pk、消息m和困难问题实例Y的有效预签名值使用正确的困难问题证据y进行适配，若得到的签名值是有效的，那么称该适配器签名方案是预签名可适配的，即

给出适配器签名方案的安全性定义.首先，延续选择消息攻击下的存在不可伪造性(existential unforgeability under chosen message attacks, EUF-CMA)的定义，考虑敌手能够访问签名预言机获取任意消息mi的合法签名值.其次，允许敌手能够访问预签名预言机获取任意消息mi和困难问题实例Y的合法预签名值.最后，对于敌手选取的挑战消息m*，允许敌手可以获取消息m*的关于实例Y的预签名值.那么，适配器方案的不可伪造性的要求就是即使敌手具备攻击能力，它在不知道困难问题证据的情况下成功伪造一个合法签名的概率是可忽略的.

定义3. aEUF-CMA安全性.一个适配器签名方案是aEUF-CMA安全的，当任意的多项式时间敌手赢得游戏的概率是可忽略的，即

定义3中，游戏的定义为：

1) 模拟器建立一个空的消息询问列表

2) 模拟器获取一个公钥pk，产生困难问题实例(IY=(Y,πY),y)←GenR(1λ)，并将(pk,IY)公布给敌手

3) 敌手可选取任意的消息mi∈{0,1}*,访问签名预言机或预签名预言机并获取相应的签名值；

4) 敌手选取一个挑战消息m*∈{0,1}*，并获取到关于m*和Y的预签名值，即

5) 敌手仍然可以选取消息mi∈{0,1}*并访问或

6) 敌手输出一个签名值σ*.若且Vrfypk(m;σ*)=1，则敌手赢得游戏.

签名预言机的工作方式为：产生一个签名值σ←Signsk(mi)，并将被签名的消息写入列表返回签名值σ.

预签名预言机的工作方式为：产生一个预签名值并将被签名的消息写入列表返回签名值

定义4. 证据可提取性(witness extractability).一个适配器签名方案是证据可提取的，当任意的多项式时间敌手赢得游戏的概率是可忽略的，即

定义4中，游戏的定义为：

1) 模拟器建立一个空的消息询问列表

2) 模拟器获取一个公钥pk和一个困难关系实例IY=(Y,πY)，并将(pk,IY)公布给敌手

3) 敌手可选取任意的消息mi∈{0,1}*,访问签名预言机或预签名预言机并获取相应的签名值；

4) 敌手选取一个挑战消息m*∈{0,1}*，并获取到关于m*和Y的预签名值，即

5) 敌手仍然可以选取消息mi∈{0,1}*并访问或

6) 敌手输出一个签名值σ*；

模拟器通过Ext算法提取y′若且(Y,y′)∉Π且Vrfypk(m;σ*)=1，则敌手赢得游戏.

显然，aWitExt游戏和aSigForge游戏较为相似，但前者与后者的区别在于尽管敌手可能成功伪造签名σ*，但提取的证据也可能不是Y的证据.

定义5. 安全适配器签名方案.一个适配器签名方案是安全的，当它满足aEUF-CMA安全性、预签名可适配性和证据可提取性.

4 基于SM2的适配器签名

在本节中，我们首先回顾下SM2数字签名方案，再给出适用于SM2算法的适配器签名方案.

一般而言，标准的SM2数字签名方案[16-17]采用素数阶的椭圆曲线点群为基本的循环群结构.不妨令是一个阶为q的椭圆曲线点群，G是的生成元，函数f(·):→q表示取中椭圆曲线点的x坐标，H(·)是一个密码杂凑函数.那么，SM2签名算法ΣSM2=(Gen,Sign,Vrfy)的描述为：

1) 密钥生成算法(sk,pk)←Gen(1λ).随机选取一个整数并计算P=d·G∈，输出私钥sk=d和公钥pk=P.

2) 签名生成算法σ←Signsk(m).对于消息m∈{0,1}*，随机选取一个整数计算K=k·G，r=H(m)+f(K) mod q和s=(1+d)-1(k-r·d) mod q，输出签名值σ=(r,s)∈q×q.

3) 签名验证算法b=Vrfypk(m;σ)：对于消息m∈{0,1}*和签名值σ=(r,s)∈q×q，验证式子r=H(m)+f(s·G+(r+s)·P)是否成立；若成立，则b=1；否则，b=0.

显然，因为s·G+(r+s)·P=(s+(1+d)-1·(k·d+r·d))·G=k·G，SM2数字签名方案的正确性是可以满足的.

假设ΠG⊆×q是群上的困难关系，即ΠG{(Y,y)|Y=y·G}，IY表示困难关系ΠG中对于状态Y的实例.为将困难关系ΠG嵌入到SM2签名方案中，我们设计了适配器签名方案：

Fig. 1 SM2-based adaptor signature scheme
图1 基于SM2的适配器签名方案

算法1. 预签名生成算法

输入：私钥d、消息m∈{0,1}*和困难关系状态Y；

输出：预签名值

① 随机选取一个整数计算K=k·G；

② 计算Q=(1+d)·Y,r=H(m)+f(K+Q) mod q和 mod q；

③ 产生零知识证明π=PY((P,Q),d)；

④ 令预签名值

算法2. 预签名验证算法

输入：公钥P、消息m∈{0,1}*、困难关系状态Y、预签名值

输出：验证结果b.

① 计算和r′=H(m)+f(K′+Q)；

② 验证式子r′=r是否成立；若成立，则br=1；否则，br=0；

③ 验证bY=VY((P,Q),π)；

④ 输出验证结果为b=br∧bY.

算法3. 适配算法σ

输入：预签名值和困难关系证据y；

输出：签名值σ.

① 计算

② 令签名值σ=(r,s).

算法4. 提取算法y′

输入：签名值σ、预签名值和困难关系状态Y；

输出：证据y′或失败符号⊥.

① 计算

② 验证(Y,y)∈ΠG是否成立；

③ 若成立，则返回y′；否则，返回⊥.

5 安全性证明

本节我们将给出基于SM2算法的适配器签名方案的安全性证明.

定理1. 基于SM2的适配器签名方案满足预签名可适配性.

证明. 对于任意的公钥P∈、困难关系实例(IY,y)∈ΠG、消息m∈{0,1}*和预签名值如果成立，则有

根据适配算法的定义，σ中的那么，

s·G-Y+(r+s-y)P+(1+d)·Y= s·G+(r+s)P.

显然，适配得到的签名值σ是一个关于公钥和消息的有效签名.

证毕.

定理2. 基于SM2的适配器签名方案满足预签名正确性.

证明. 给定私钥d、困难问题证据y和消息m∈{0,1}*，则有P=d·G和Y=y·G.对于pSignsk(m,Y)产生的预签名值有则r′=r必然成立.又根据非交互式零知识证明的完备性，VY((P,Q),π)=1也成立.因此，

根据定理1，可知Vrfypk(m;σ)=1.再根据适配算法的定义可知，和s间只差一个y.那么，通过提取算法还原的y′必然是Y的证据，即(Y,y′)∈ΠG.

证毕.

定理3. 如果SM2签名方案ΣSM2是EUF-CMA安全的，且ΠG是一个困难关系，则基于SM2的适配器签名方案满足aEUF-CMA安全性.

证明. 假设敌手与模拟器进行aSignForge游戏，其中会向进行哈希询问签名询问和预签名询问而能够访问SM2签名方案的签名预言机来响应询问，并控制随机预言机和预签名预言机来响应询问.按照aSignForge游戏的定义，敌手与模拟器进行交互：

1) 模拟器初始化一个空的消息询问列表和一个空的哈希询问列表

2) 模拟器询问SM2签名方案的签名预言机获取公钥pk，产生困难关系(IY=(Y,πY),y)←GenR(1λ)，并发送(pk,IY)给敌手

3) 敌手自适应的选取消息mi∈{0,1}*，进行哈希询问、签名询问和预签名询问，模拟器的响应方式为：

哈希询问当询问x的哈希值时，先查询列表中是否存在H(x)；若存在，则直接取出；否则，随机产生H(x)←$ 并将(x,H(x))存入列表中；最后，返回H(x)给

签名询问当询问mi的签名值时，直接向发起关于mi的签名询问，并将获取的签名值σ返回给

预签名询问当询问mi和IY的预签名值时，按照步骤进行响应：

① 对发起关于mi的签名询问，获取签名值σ=Signsk(mi)；

② 计算和Q=Y+y·P；

③ 模拟零知识证明πS=S((P,Q),1)；

④ 更新列表

⑤ 输出预签名值

之后，将返回给

4) 敌手选取一个挑战消息m*∈{0,1}*，并询问关于m*和Y的预签名值，按照预签名询问进行响应；

5) 敌手仍可自适应的选取消息mi∈{0,1}*，进行3)中的询问；

6) 敌手输出一个签名值σ*.模拟器收到σ*后，检查是否成立；若成立，则报错退出.

如果签名值σ*是有效的且m*未出现在列表中，那意味着可以将(m*,σ*)作为一个合法的消息-签名对攻击SM2签名方案的不可伪造性.

优势分析：由于模拟器只可能在步骤6)中退出，且该情况发生时隐含敌手可通过Ext算法从σ*和中获取证据y，其概率是可忽略的.那么，敌手的优势是也是可忽略的.

证毕.

定理4. 如果SM2签名方案ΣSM2是EUF-CMA安全的，且ΠG是一个困难关系，则基于SM2的适配器签名方案满足证据可提取性.

证明. 假设敌手与模拟器进行aWitExt游戏，其中会向进行哈希询问签名询问和预签名询问而能够访问SM2签名方案的签名预言机来响应询问，并控制随机预言机和预签名预言机来响应询问.按照aSignForge游戏的定义，敌手与模拟器进行交互：

1) 模拟器初始化一个空的消息询问列表和一个空的哈希询问列表

2) 模拟器询问SM2签名方案的签名预言机获取公钥pk并发送给敌手同时，敌手获取到困难问题实例IY=(Y,πY)；

3) 敌手自适应的选取消息mi∈{0,1}*，进行哈希询问、签名询问和预签名询问，模拟器的响应方式为：

哈希询问当询问x的哈希值时，先查询列表中是否存在H(x)；若存在，则直接取出；否则，随机产生H(x)←$ 并将(x,H(x))存入列表中；最后，返回H(x)给

签名询问当询问mi的签名值时，直接向发起关于mi的签名询问，并将获取的签名值σ返回给

预签名询问当询问mi和IY的预签名值时，按照步骤进行响应：

① 通过NIZK方案的在线提取器获取证据y，即y如果(Y,y)∉ΠG，则报错退出；

② 对发起关于mi的签名询问，获取签名值σ=Signsk(mi)；

③ 计算和Q=Y+y·P；

④ 模拟零知识证明πS=S((P,Q),1)；

⑤ 更新列表

⑥ 输出预签名值

之后，将返回给A.

4) 敌手选取一个挑战消息m*∈{0,1}*，并询问关于m*和Y的预签名值，按照预签名询问进行响应；

5) 敌手仍可自适应的选取消息mi∈{0,1}*，进行3)中的询问；

6) 敌手输出一个签名值σ*.

如果签名值σ*是有效的且m*未出现在列表中，那意味着可以将(m*,σ*)作为一个合法的消息-签名对攻击SM2签名方案的不可伪造性.

优势分析：由于模拟器只可能在3)中①)退出，且该情况发生的概率是可忽略的.那么，敌手的优势是也是可忽略的.

证毕.

定理5. 如果SM2签名方案ΣSM2是EUF-CMA安全的，且ΠG是一个困难关系，则基于SM2的适配器签名方案是安全的.

证明. 显然，根据定义5和定理1～4可知，基于SM2的适配器签名方案是安全的.

证毕.

6 效率分析

本节我们以计算开销和通信开销来评估基于SM2的适配器签名方案的效率,并将评估结果与文献[8]中的基于Schnorr的适配器签名方案和基于ECDSA签名方案进行比较.

6.1 计算开销分析

在计算开销方面，我们主要考虑预签名生成算法、预签名验证算法、适配算法和提取算法的计算开销.对于密钥生成算法而言，SM2,Schnorr和ECDSA的密钥生成机制是一样的，故不作比较.表1给出了3种方案计算开销，其中TP和TV分别使用NIZK证明生成算法和验证算法的计算耗时，Tpm和Tpa分别表示群中点乘和点加运算的计算耗时，Tinv,Tmul和Tadd分别表示中模逆、模乘和模加运算的计算耗时，Th表示一次杂凑运算的计算耗时.由于，Tadd在pSign和pVrfy算法中的占比极低，故可忽略.另外，SM2算法中的(1+d)-1可预计算，故该运算亦可忽略.

Table 1 Comparisons of Computation Costs for Different Adaptor Signature Schemes
表1 不同适配器签名方案的计算开销比较

对于预签名生成算法而言，SM2适配器签名方案比Schnorr适配器签名方案多1个NIZK证明、1个点乘和1个模乘，比ECDSA适配器签名方案多1个模乘、少1个模逆.从图2中可知，SM2适配器签名方案的预签名生成耗时与ECDSA适配器签名方案相当，但是Schnorr适配器签名方案的3.2倍.

Fig. 2 Execution time of different adaptor signature schemes
图2 不同适配器签名方案的运行耗时

对于预签名验证算法而言，SM2适配器签名方案比Schnorr适配器签名方案多1个NIZK验证和2个模乘，少1个点乘，比ECDSA适配器签名方案少1个模逆.从图2中可知，SM2适配器签名方案的预签名验证耗时与ECDSA适配器签名方案相当，但是Schnorr适配器签名方案的2.3倍.

对于适配算法和提取算法而言，SM2适配器签名方案和Schnorr适配器签名方案均采用了加法形式构造，其所调用的模加/减运算几乎可以忽略不计.而ECDSA适配器签名方案采用乘法方式构造，需要调用1次模逆和1次模乘，其运算量远大于另外2个方案.

6.2 通信开销分析

在通信开销方面，我们主要考虑预签名值的尺寸.对于参与比较的3个适配器签名方案，其私钥、公钥和签名值尺寸是一样的.

如表2所示，SM2适配器签名方案和ECDSA适配器签名方案的预签名值尺寸为4|q|+||(192 B)，其中NIZK证明需要2个q上的元素表示.Schnorr适配器签名方案的预签名值尺寸为2|q|(64 B).

Table 2 Comparisons of Communication Costs for Different Adaptor Signature Schemes
表2 不同适配器方案的通信开销比较

SM2适配器签名方案在计算和通信开销方面与ECDSA适配器签名方案相当，但在适配算法和提取算法的计算开销方面更优；SM2适配器签名方案的运算性能约为Schnorr适配器签名方案的一半，且预签名值尺寸为Schnorr适配器签名方案的3倍.

7 结 论

作为标准数字签名方案的一种扩展，适配器签名可以在签名逻辑中内联困难问题，并限制完整签名的获取条件.该功能已经成为了区块链系统中链下支付通道构建的关键模块.然而，现在的适配器签名方案均以国外算法为原型，缺少基于国家商用密码标准的适配器签名方案.为此，本文以SM2数字签名方案为基础，构造了一个新的适配器签名方案，并在随机预言模型下证明其满足适配器签名方案的安全要求.通过性能分析，可知所提出的适配器签名方案的性能与基于ECDSA的适配器签名方案相当，且在适配算法和提取算法的计算开销方面具有极大的优势.下一步，我们将以本文的方案为出发，试图构造基于SM2的指定提取者适配器签名方案、盲适配器签名方案和环适配器签名方案等.