彭 聪 罗 敏 何德彪 黄欣沂

1(武汉大学国家网络安全学院 武汉 430072) 2(福建师范大学计算机与网络空间安全学院 福州 350117)

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

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.3 困难关系

令Π是一种二元关系，LΠ是描述这种关系的语言，即LΠ{Y|∃ys.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 系统模型

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

3.2 安全模型

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

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

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

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

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

4 基于SM2的适配器签名

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

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

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的适配器签名方案

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

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

输出：验证结果b.

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

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

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

算法3.适配算法σ

输出：签名值σ.

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

算法4.提取算法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的适配器签名方案满足预签名正确性.

证毕.

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

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

证毕.

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

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

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

证毕.

定理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可预计算，故该运算亦可忽略.

对于预签名生成算法而言，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的指定提取者适配器签名方案、盲适配器签名方案和环适配器签名方案等.