基于双线性配对的适配器签名方案*

王子瑞， 张 驰， 魏凌波，2

1. 中国科学技术大学 网络空间安全学院， 合肥 230022

2. 中国电子科技南湖研究院， 嘉兴 314002

适配器签名(adaptor signature) 是在数字签名基础上扩展而来的一类密码学原语[1]. 它允许用户生成一个隐含困难关系声明的预签名， 只有利用困难关系见证才可以将预签名转换为一个验证合法的全签名， 而使用预签名和相应的全签名就可以提取困难关系的见证. 这里的全签名使用标准签名方案的验证算法来验证其有效性. 也就是说， 适配器签名中所包含的预签名、全签名和困难关系的见证这三者满足如下的性质， 即只有知道其中任意两个的值， 才能算出第三个的值. 适配器签名的这个性质配合上区块链的交易(含签名) 在上链被确认后即公开有效的特性， 可以用来实现各种不依赖于可信第三方的原子交换(交换双方或者都获得了各自的交换对象， 或者都没有所获， 也称为公平交换[2]).

假设只有Alice 知道一个离散对数关系Y=gy(这是一个典型的困难关系) 的见证y， Alice 希望用这个秘密见证y向Bob 换取Bob 的私钥x对消息m的数字签名， 而且这个签名必须公开发布才能产生效力(例如这是上链交易的签名). Bob 首先利用公开的困难关系声明Y和自己的私钥x生成对消息m的预签名， 并发送给Alice. 由于Alice 知道见证y， 她可以将Bob 发来的预签名转换为Bob 的私钥x对消息m的全签名(Alice 还可以使用Bob 的公钥来验证这个全签名的有效性)， 同时为了使得这个签名生效， Alice 必须将包含这个全签名的交易在区块链上公开. Bob 一旦看到区块链上公开的全签名， 再加上自己生成的预签名， 就能得到见证y. 在上述交换过程中， 无论哪一方在任何一个步骤偏离或者主动退出交换协议， 都会导致双方一无所获， 从而保证了交易的原子性.

适配器签名还可用于实现跨链的加密货币原子交换[1]. 假设Alice 希望用1 比特币换取Bob 的13以太币. Alice 首先将1 比特币锁定到一个与Bob 商定的2-of-2 的比特币地址中， 并且规定如果超出一个较长的时间后， 该地址中的比特币还没有被花费， 则1 比特币返还到原先Alice 的地址. 随后Alice 构建比特币交易TX1， 将2-of-2 地址中的1 比特币输出到Bob 指定的地址中， TX1解锁的条件是同时提供Alice 和Bob 对该交易的签名. Bob 对应地将13 以太币锁定在以太坊上由Alice 和Bob 共同管理的账户中， 同时规定如果超出一个较长的时间后， 该账户中的以太币还没有被花费， 则13 以太币返还到原先Bob的账户. 随后Bob 构建以太坊交易TX2， 将共管账户中的13 以太币输出到Alice 指定的账户中， TX2解锁的条件是同时提供Alice 和Bob 对该交易的签名. 剩下的任务就是使得两个交易TX1和TX2分别在各自的区块链上一起生效或都不生效(从而保证交换的原子性).这两个交易生效的关键都是除了己方的签名外， 还需要对方对各自交易的签名. 双方都可以按照上述的适配器签名方案针对不同的交易生成预签名，这些预签名通过相同的离散对数关系Y=gy绑定起来， 一旦知晓见证y的一方利用y将某一预签名转换为自己所需的全签名， 并在对应的区块链上公开交易(以及相应的全签名)， 另一方就可以通过观察到的公开信息来计算见证y， 从而获得自己所需的全签名， 然后在另一个区块链上发布对应的交易.

在适配器签名出现之前， 完成类似的原子交换功能需要将交换逻辑通过区块链所支持的脚本语言显式地写入能在区块链上运行的智能合约之中[3]. 使用适配器签名的原子交换则与此不同， 关键的交换步骤其实是在链下完成的， 而且除了最简单的区块链交易所必须支持的数字签名类脚本之外， 不需要再使用其它类型的脚本， 因而这类实现方法也被比特币社区称为隐形脚本(scriptless script) 或最小化脚本(miniscript). 与大量使用显示脚本的智能合约相比， 基于适配器签名的实现方法有以下优点: 首先， 由于上链的信息被最小化， 而且上链的交易与最普通的区块链交易外观相同， 无法被第三方区分开来， 相关交易的适配器签名也无法被关联起来， 从而在最大程度上保护了交换参与者的隐私. 其二， 由于需要上链执行的脚本大大减少， 节约了交易参与方的交易费用， 也有利于改善区块链系统整体的可扩展性. 其三， 由于不需要特殊的脚本语言来支持， 这种方法的普适性最强， 只要区块链所使用的签名方案可以扩展为适配器签名， 这种方法就可以实施. 相反， 不同的区块链所支持的脚本语言在功能上都有很大的差异， 在一个区块链上能够用智能合约实现并不意味着在另一个区块链上也能够实现. 正是由于上述的显著优势， 适配器签名已经成为了区块链理论和应用研究中的一大热点.

适配器签名的构想最初是在2017 年由Poelstra 在比特币研究社区的讨论中提出的[4]， 随后这一技术被广泛应用于支付通道[5，6]、跨链原子交换[7，8]等众多的区块链应用场景之中， 但是Poelstra 和随后的应用研究并没有给出适配器签名的形式化定义与安全模型. Fournier 在2019 年基于Boneh 等人提出的可验证加密签名(verifiably encrypted signature， VES) 的概念[9]， 首次将适配器签名定义为一次性的VES[1]， 并给出了安全模型. Aumayr 等人则是在2021 年将适配器签名作为一个独立的密码学原语[5]，给出了形式化的定义和目前普遍使用的安全模型. 他们还基于区块链常用的Schnorr 数字签名算法[10]和椭圆曲线数字签名算法(elliptic curve digital signature algorithm， ECDSA)[11]构造了具体的适配器签名方案， 并给出了安全证明， 从而为适配器签名在区块链中的广泛应用奠定了坚实的理论基础.

如前所述， 适配器签名能否被应用的关键在于区块链所使用的底层数字签名方案扩展成为适配器签名的可能性. 因而除了将目前的主流区块链所使用的签名方案(如ECDSA 等) 扩展为适配器签名以外， 一个主要的研究方向就是考察其它有望用于区块链的数字签名体制能否扩展为适配器签名. Erwig 等人系统研究了基于身份识别协议的数字签名方案， 并提出了将这类数字签名扩展为适配器签名的通用方法[12].Peng 等人则研究并实现了将国密数字签名SM2 扩展为适配器签名的方案[13]. 面向区块链对抗量子攻击的数字签名的需求， Esgin 等人基于格密码[14]、Tairi 等人基于同源映射密码[15]分别构造了后量子安全的适配器签名方案. 基于双线性配对(bilinear pairing) 的数字签名是另外一类有望在区块链中获得广泛应用的密码体制. 双线性配对作为在椭圆曲线上可有效计算的双线性二元映射， 是一种优秀的密码学算法构造工具[16]. 以此为基础， 密码学家已经构造出了性能优异的短签名(BLS 签名)[17]和带有其它强大功能的签名(如聚合签名、可验证的加密签名、部分盲签名等). 在比特币社区一直有将BLS 签名列为标准签名的规划. Boneh 等人则在2018 年为比特币区块链专门设计了基于双线性配对的可聚合的多签名[18].2020 年发布的以太坊2.0 规范已经包括了BLS 签名. 这就引发了一个重要问题: 基于双线性配对的数字签名是否可以扩展为适配器签名？针对这一问题， Erwig 等人在2021 年首先给出了负面的结果: 他们主要是针对BLS 签名这类确定型的数字签名， 在理论上证明这类签名不能扩展为适配器签名[12].

本文通过给出一个具有可证明安全的适配器签名方案， 说明基于双线性配对的数字签名方案可以扩展为适配器签名方案， 从而极大地扩展了适配器签名在区块链系统中的应用范围. 由于Erwig 等人已经证明确定型数字签名不能用于扩展适配器签名， 本文首先设计了一个基于双线性配对的概率型数字签名方案(见第4 节)， 在尽量保留BLS 短签名优点的前提下， 在签名中引入随机因子， 并与扩展后需要嵌入的困难关系保持同样的代数结构. 然后将该数字签名方案扩展为适配器签名方案(见第5 节)， 确保预签名不能透露全签名的任何信息， 即只有预签名不能伪造一个有效的全签名; 预签名还要具有适配性， 即利用预签名和见证y可以计算得到一个验证合法的全签名. 全签名还要具有见证可提取性， 即利用全签名、预签名可以计算得到见证y. 最后， 在第6 节还将所设计方案的安全性和性能开销与文献中有代表性的适配器签名方案进行了全面的比较.

本节给出本文需要使用的双线性配对、困难关系假设和困难关系的定义.

定义1 (双线性配对) : 设G 和GT均为阶是大素数q的循环群. 称映射e:G×G→GT为双线性配对， 如果e满足以下性质:

(1) 双线性: 对于任意x，y ∈G 和任意a，b ∈Zq， 都有e(xa，yb)=e(x，y)ab.

(2) 非退化: 若g是群G 的生成元， 则e(g，g)/=1GT.

(3) 可计算: 对于任意x，y ∈G，e(x，y)∈GT可被有效计算.

定义2 (计算Diffie-Hellman 问题) : 对于任意的a，b ∈Z*q， 给定(g，ga，gb)， 计算gab.

若对任意概率多项式时间敌手A， 都有Pr[h ←A(n，g，ga，gb):h=gab]≤negl(n) (negl 是一个关于安全参数n可忽略函数)， 则称在循环群G 上计算Diffie-Hellman 问题是困难的.

定义3 (困难关系): 设R为(Y，y) 所满足的一个二元关系， 其中Y被称作声明，y被称作见证. 记LR:={Y|∃ys.t. (Y，y)∈R}是描述R的语言. 称R为一个困难关系， 若R满足以下性质:

(1) 存在一个概率多项式时间算法GenR， 输入安全参数n， 输出(Y，y)∈R.

(2) 存在一个确定多项式时间算法能够判定(Y，y)∈R或(Y，y) /∈R.

(3) 对任意多项式时间的敌手和任意Y ∈LR， 计算y使得(Y，y)∈R的概率可忽略.

本文具体所使用的困难关系R为离散对数困难关系， 即声明与见证对(Y，y) 满足Y=gy. 当需要运行算法GenR 得到一组离散对数困难关系实例时， 输入安全参数n， 此时算法随机选取y ∈Z*q， 计算Y=gy， 输出(Y，y).

本节首先回顾数字签名算法及其安全模型， 然后介绍适配器签名算法和其安全模型. 在后面的章节中将根据这些定义构造具体的数字签名方案和适配器签名方案并给出安全证明.

3.1 数字签名算法及其安全模型

定义4 (数字签名):一个数字签名方案SIG=(KeyGen，Sign，Vrfy)，包含密钥生成算法KeyGen、签名算法Sign 和签名验证算法Vrfy.

· KeyGen(1n): 输入安全参数n， 输出一对公私钥对(pk，sk).

· Sign(sk，m): 输入消息m和私钥sk， 输出对消息m的签名σ.

· Vrfy(pk，m，σ): 输入消息m、签名σ和公钥pk， 输出一个比特值b ∈{0，1}，b=1 表示接受该签名，b=0 表示拒绝该签名.

一个数字签名方案SIG 最基本的安全要求是要满足选择消息攻击下存在不可伪造性(existential unforgeability against chosen message attacks， EUF-CMA)[19]， 这一安全性质是由挑战者C和敌手A之间交互的游戏SigForgeA，SIG(n) 来定义的， 具体过程如下:

(1) 初始化阶段: 挑战者C运行KeyGen(1n) 生成公私钥对(pk，sk)， 将pk 交给敌手A， 保留sk 以回答敌手的签名询问.

(2) 签名询问阶段:敌手A自适应地选择消息mi向挑战者C询问签名.挑战者C运行Sign(sk，mi)，得到签名σi并发送给敌手A.

(3) 签名伪造阶段: 敌手A给出伪造签名的消息m*和伪造的签名σ*.

若验证σ*合法且敌手未询问过消息m*的签名， 则敌手赢得游戏， 输出1; 否则， 输出0.

定义5 (EUF-CMA): 若对任意概率多项式时间的敌手A， 运行游戏SigForgeA，SIG(n)， 敌手A赢得游戏的概率是可忽略的， 即

则称数字签名方案SIG 是EUF-CMA 安全的.

3.2 适配器签名算法及其安全模型

定义6 (适配器签名): 一个基于困难关系R和签名方案SIG=(KeyGen， Sign， Vrfy) 的适配器签名方案aSIGR，SIG除了包含原有签名方案SIG 的三个算法外， 还包含五个新的算法， 即困难关系生成算法GenR、预签名算法pSign、预签名验证算法pVrfy、适配算法Adapt 和见证提取算法Ext.

· GenR(1n): 输入安全参数n， 输出一个声明见证对(Y，y)∈R.

· pSign(sk，m，Y): 输入私钥sk、消息m ∈{0，1}*和声明Y， 输出一个预签名～σ.

· pVrfy(pk，m，Y，～σ): 输入公钥pk、消息m ∈{0，1}*、声明Y和预签名～σ， 输出一个比特值b ∈{0，1}，b=1 表示预签名合法，b=0 表示预签名不合法.

· Adapt(～σ，y): 输入预签名～σ和见证y， 输出一个全签名σ.

· Ext(σ，～σ，Y): 输入全签名σ、预签名～σ和声明Y ∈LR， 输出一个见证y使得(Y，y)∈R.

一个适配器签名方案aSIGR，SIG是安全的， 如果它满足以下三个性质: 选择消息攻击下存在不可伪造性(existential unforgeability against chosen message attacks for adaptor signature， aEUF-CMA)、预签名适配性(pre-signature adaptability) 和见证可提取性(witness extractability)[5]. 下面分别给出三个性质的定义.

3.2.1 aEUF-CMA

aEUF-CMA 安全是适配器签名方案最重要的安全性质， 它保证了任何不具有见证y的人， 即使可以获取针对消息m的有效的预签名， 也难以伪造针对消息m的一个全签名. 适配器签名的aEUFCMA 安全与数字签名的EUF-CMA 安全类似， 也是通过挑战者C和敌手A之间交互的游戏aSig-ForgeA，aSIGR，SIG(n) 来定义的， 具体如下:

(1) 初始化阶段:挑战者C运行KeyGen(1n)生成公私钥对(pk，sk)，运行GenR(1n)生成(Y，y)∈R，将pk 和Y交给敌手A， 保留sk 以回答敌手的预签名和签名询问.

(2) 预签名询问阶段: 敌手A自适应地选择消息mi作预签名询问， 挑战者将消息mi加入消息询问列表Q， 运行pSign 算法， 将mi和对应的预签名～σi发送给敌手.

(3) 签名询问阶段: 敌手A自适应地选择消息mi作签名询问， 挑战者将消息mi加入消息询问列表Q， 运行Sign 算法， 将mi和对应的签名σi发送给敌手.

(4) 全签名伪造阶段: 敌手A选择要伪造全签名的消息m*发送给挑战者C. 挑战者C运行pSign(sk，m*，Y) 得到预签名～σ*， 发送给敌手A. 敌手A给出针对消息m*的伪造签名σ*.

若Vrfy(pk，m*，σ*)=1 且m*/∈Q， 则敌手赢得游戏， 输出1; 否则， 输出0.

定义7 (aEUF-CMA): 若对任意概率多项式时间的敌手A， 运行游戏aSigForgeA，aSIGR，SIG(n)， 敌手A赢得游戏的概率是可忽略的， 即

则称适配器签名方案aSIGR，SIG是aEUF-CMA 安全的.

3.2.2 预签名适配性

预签名适配性是使得预签名能够提供原子交换功能的第一个关键性质， 它保证了任何拥有见证y的人， 只要获取到在相应声明Y下验证合法的预签名， 就一定可以将该预签名转换为在原有签名验证算法下验证合法的全签名. 预签名适配性的规范化定义表述如下.

定义8 (预签名适配性): 若对任意消息m ∈{0，1}*、任意公钥pk、任意(Y，y)∈R和预签名～σ， 当预签名验证合法， 即满足pVrfy(pk，m，Y，～σ)=1 时， 使用预签名～σ和见证y计算得到的全签名一定合法，即满足Vrfy(pk，m，Adapt(～σ，y))=1， 则称该适配器签名方案满足预签名适配性.

3.2.3 见证可提取性

见证可提取性是使得预签名能够提供原子交换功能的第二个关键性质， 它保证了获取到一对验证合法的预签名与全签名对的用户可以从中提取秘密见证y. 见证可提取性是通过挑战者C和敌手A之间交互的游戏WitExtA，aSIGR，SIG(n) 来定义的， 具体如下:

(1) 初始化阶段: 挑战者C运行KeyGen(1n) 生成公私钥对(pk，sk)， 将pk 交给敌手A， 保留sk 以回答敌手的预签名询问和签名询问. 敌手A运行GenR 算法生成(Y，y)∈R， 公布声明Y， 保密见证y.

(2) 预签名询问阶段: 敌手A自适应地选择消息mi作预签名询问， 挑战者将消息mi加入消息询问列表Q， 运行pSign 算法， 将mi和对应的预签名～σi发送给敌手.

(3) 签名询问阶段: 敌手A自适应地选择消息mi作签名询问， 挑战者将消息mi加入消息询问列表Q， 运行Sign 算法， 将mi和对应的签名σi发送给敌手.

(4) 见证提取阶段: 敌手A选择消息m*和Y*， 发送给挑战者C. 挑战者C运行pSign(sk，m*，Y*)，得到预签名～σ*， 发送给敌手A. 敌手A生成针对消息m*的签名σ*， 交给挑战者C. 挑战者C运行Ext(σ*，～σ*，Y*)， 得到见证y′.

若Vrfy(pk，m*，σ*)=1， 同时m*/∈Q且(Y*，y′) /∈R， 则敌手赢得游戏， 输出1; 否则， 输出0.

定义9 (见证可提取性): 若对任意概率多项式时间的敌手A， 运行游戏WitExtA，aSIGR，SIG(n)， 敌手A赢得游戏的概率是可忽略的， 即

则称适配器签名方案aSIGR，SIG满足见证可提取性.

游戏WitExt 和游戏aSigForge 非常相似， 然而有一个重要的不同点是在游戏WitExt 中是由敌手A来运行GenR 算法. 因此， 敌手A可能知道对应的见证y*， 可以利用y*和预签名～σ*给出消息m*的一个签名σ*. 然而敌手A要赢得游戏WitExt 的要求是给出的签名不能泄露见证y的信息.

本节首先构造一个基于双线性配对的概率型数字签名方案Π， 作为下一节扩展为适配器签名方案的基础， 然后基于计算Diffie-Hellman 困难问题假设， 在随机预言机模型下证明该方案是EUF-CMA 安全的.

设H:{0，1}*→G 是抗碰撞的哈希函数，e: G×G→GT是第2 节中定义的双线性配对， 数字签名方案Π 构造如下:

· KeyGen(1n): 签名者随机选取x ∈Z*q， 计算h=gx. 令(pk，sk)=(h，x)， 公开pk， 保密sk.

· Sign(sk，m): 签名者随机选取r ∈Z*q， 计算R=gr， 令(σ1，σ2) =(r，H(R||m)x)， 输出对消息m的签名(σ1，σ2).

· Vrfy(pk，m，σ1，σ2): 若e(σ2，g)=e(H(gσ1||m)，h)， 签名合法， 输出1; 否则， 签名不合法， 输出0.

定理1 设哈希函数H是一个随机预言机. 若计算Diffie-Hellman 问题是困难的， 则上述数字签名方案Π 满足EUF-CMA.

证明: 若存在敌手A在多项式时间赢得游戏SigForgeA，Π(n)， 则可以构造一个模拟器S在多项式时间成功求解计算Diffie-Hellman 问题. 随机预言机由模拟器S控制， 模拟器S依照如下过程为敌手A模拟游戏SigForgeA，Π(n)， 其中p1和p2均是关于安全参数n的多项式.

(1) 初始化阶段: 挑战者C生成一个群G 上计算Diffie-Hellman 问题的实例(g，ga，gb)， 交给模拟器S. 模拟器S设置pk=h=ga， 相应的私钥sk=a， 将pk 交给敌手A.

因为假定计算Diffie-Hellman 问题是困难的， 所以数字签名方案Π 满足EUF-CMA.

本节基于第4 节中的数字签名方案Π 构造适配器签名方案， 并证明其满足第3 节中定义的适配器签名的三个安全性质.

一个基于离散对数关系Rg和数字签名方案Π 的适配器签名方案ΞΠ构造如下:

· GenR(1n): 验证者随机选取y ∈Z*q， 计算Y=gy， 输出声明与见证对(Y，y)∈Rg. 验证者将声明Y发给签名者.

· pSign(sk，m，Y): 签名者使用该算法生成对消息m的预签名. 随机选取r ∈Z*q， 计算R=gr， 令(～σ1，～σ2)=(r，H(RY||m)x)， 输出对消息m的预签名(～σ1，～σ2).

· pVrfy(pk，m，Y，～σ1，～σ2): 验证者使用该算法验证签名者生成的对消息m的预签名是否合法. 若e(～σ2，g)=e(H(g～σ1Y||m)，h)， 预签名合法， 输出1; 否则， 预签名不合法， 输出0.

· Adapt(～σ1，～σ2，y): 验证者使用该算法提取签名者对消息m全签名. 计算σ1= ～σ1+y，σ2= ～σ2， 输出(σ1，σ2).

· Ext(σ1，～σ1，Y): 一旦验证者公布了全签名(σ1，σ2)， 签名者就可使用该算法提取原本只有验证者知晓的见证值y. 计算y=σ1-～σ1， 输出y.

定理2 设哈希函数H是一个随机预言机. 若计算Diffie-Hellman 问题是困难的， 则上述适配器签名方案ΞΠ满足aEUF-CMA.

证明: 若存在敌手A在多项式时间赢得游戏aSigForgeA，ΞΠ(n)， 则可以构造一个模拟器S在多项式时间成功求解计算Diffie-Hellman 问题. 随机预言机由模拟器S控制， 模拟器S为敌手A模拟aSigForgeA，ΞΠ(n) 过程， 游戏模拟按照如下过程进行， 其中p1，p2，p3均是关于安全参数n的多项式.

(1) 初始化阶段: 挑战者C生成一个群G 上计算Diffie-Hellman 问题的实例(g，ga，gb)， 交给模拟器S. 模拟器S设置pk =h=ga， 相应的私钥sk =a. 模拟器S运行GenR(1n) 生成一个声明与见证对(Y，y) 满足Y=gy， 将pk，Y交给敌手A. 消息询问集合Q初始化为空.

若(σ1，σ2) 验证合法且消息m*/∈Q， 则敌手成功伪造了签名. 由于预签名算法pSign 和签名算法Sign 都是概率算法， 因此安全模型中并不要求模拟器S给出的预签名和敌手A伪造的签名是匹配的， 只需要模拟器S提供的预签名通过pVrfy 算法验证即可. 也就是说， 即使敌手A成功伪造了签名， 也可能无法用该签名提取见证y.

因为假定计算Diffie-Hellman 问题是困难的， 所以适配器签名方案ΞΠ满足aEUF-CMA.

定理3 上述适配器签名方案ΞΠ满足预签名适配性.

证明: 对任意消息m ∈{0，1}*， 任意公钥h=gx， 任意(Y，y) 满足Y=gy， 预签名(～σ1，～σ2) =(r，H(grY||m)x)， 满足pVrfy(pk，m，Y，～σ1，～σ2) = 1， 即e(H(grY||m)x，g)=e(H(grY||m)，h). 则签名(σ1，σ2) = Adapt(～σ1，～σ2，y) =(r+y，H(grY||m)x)， 所以e(H(grY||m)x，g)=e(H(gr+y||m)，h)， 即Vrfy(pk，m，Adapt(～σ1，～σ2，y))=1. 因此适配器签名方案ΞΠ满足预签名适配性.

定理4 上述适配器签名方案ΞΠ满足见证可提取性.

证明: 若存在敌手A在多项式时间赢得游戏WitExtA，ΞΠ(n)， 则可以构造一个模拟器S在多项式时间内找到哈希函数H的一对碰撞. 模拟器S为敌手A模拟游戏WitExtA，ΞΠ(n). 游戏模拟按照如下过程进行.

(1) 初始化阶段: 模拟器S运行KeyGen 算法生成公私钥对(pk，sk)=(gx，x)， 将公钥pk 交给敌手A， 保留sk 以回答敌手A的预签名询问和签名询问. 敌手A运行GenR 算法生成声明与见证对(Y，y) 满足Y=gy， 将声明Y交给模拟器S. 消息询问集合Q初始化为空.

(2) 预签名询问阶段: 敌手A在此阶段可以向模拟器S作预签名询问. 假设敌手A针对消息mi作预签名询问， 模拟器S运行pSign 算法生成关于消息mi的预签名(～σ1，～σ2) 发给敌手A， 并将消息mi加入集合Q.

(3) 签名询问阶段: 敌手A在此阶段可以向模拟器S作签名询问. 假设敌手A针对消息mi作签名询问， 模拟器S运行Sign 算法生成关于消息mi的签名(σ1，σ2) 发给敌手A， 并将消息mi加入集合Q.

(4) 见证提取阶段: 敌手A选择消息m*∈{0，1}*， 发送给模拟器S. 模拟器S运行pSign 算法生成消息m*的预签名(～σ*1，～σ*1) 发送给敌手A. 敌手A产生一个消息m*的签名(σ*1，σ*2) 交给模拟器S. 模拟器S运行Ext 算法提取见证y′.

若Vrfy(par，m*，σ*1，σ*2，pk)=1 且m*/∈Q且Y/=gy′， 则敌手赢得游戏， 输出1; 否则， 输出0.

设～σ*1=r. 模拟器S提取见证得到y’ 后， 将比特串gr+y′||m*和grY||m*发送给挑战者C作为哈希函数H的一对碰撞.

下面分析模拟器S成功给出哈希函数H一对碰撞的概率. 已知(r，H(grY||m*)x)是模拟器S给出的关于消息m*的一个合法的预签名. 若游戏输出1， 则模拟器S成功提取了见证y′使得Y/=gy′且(r+y′，H(grY||m*)x)是一个合法的全签名. 同时，(r+y′，H(gr+y′||m*)x)也一定是一个合法的全签名.因此，一定有e(H(gr+y′||m*)x，g)=e(H(grY||m*)x，g).这时，若H(gr+y′||m*)/=H(grY||m*)，那么双线性配对e将不满足定义1 中的非退化. 因此， 当游戏输出1 时， 一定会有H(gr+y′||m*)=H(grY||m*).而Y/=gy′， 所以gr+y′||m*和grY||m*是两个不同的比特串， 这正是哈希函数H的一对碰撞. 所以， 模拟器S成功给出哈希函数H的一对碰撞的概率

因为哈希函数H满足抗碰撞性， 所以适配器签名方案ΞΠ满足见证可提取性.

下面将本文方案与基于Schnorr 签名的适配器签名方案和基于ECDSA 的适配器签名方案在安全性、计算开销与存储开销方面进行比较. 后两种方案也是目前区块链系统中使用最为广泛的适配器签名方案.

在安全性方面，基于Schnorr 签名的适配器签名方案将aEUF-CMA 安全归约到Schnorr 签名的强不可伪造性[5]，Kiltz 等人[20]将Schnorr 签名的强不可伪造性归约到离散对数问题的困难性.基于ECDSA的适配器签名方案将aEUF-CMA 安全归约到ECDSA 的强不可伪造性[5]， 然而ECDSA 的强不可伪造性至今没有得到证明， 因此基于ECDSA 的适配器签名方案的安全性没有理论上的保障. 本文方案将aEUF-CMA 安全归约到计算Diffie-Hellman 问题的困难性， 计算Diffie-Hellman 困难问题是目前基于双线性配对的方案中常用的困难问题假设.

在计算开销方面， 比较以上三种方案中pSign、pVrfy、Adapt、Ext 算法的计算时间， 详细的计算开销对比见表1. 其中，Tp与Tv分别表示生成与验证零知识证明的计算时间;Tgp和Tgm分别表示循环群G 中幂运算与乘运算的计算时间;Tinv、Tmul、Tadd分别表示Z*q中模逆、模乘、模加的计算时间;Tpair、Th1、Th2分别表示双线性配对e， 哈希函数H1:{0，1}*→Z*q， 哈希函数H2:{0，1}*→G 的计算时间.

表1 计算开销对比Table 1 Computational cost comparison

使用MacbookPro 笔记本电脑运行以上三种适配器签名方案. 笔记本电脑使用的中央处理器为IntelCore i5@2.70 GHz， 内存为8 GB. 得到这三种方案在pSign、pVrfy、Adapt、Ext 算法中的具体计算时间， 如图1 所示.

图1 计算时间对比Figure 1 Computational time comparison

本文方案pSign 算法的计算耗时比基于Schnorr 签名的适配器签名方案多1.188 ms， 然而比基于ECDSA 的适配器签名方案少1.948 ms. 本文方案Adapt 算法和Ext 算法的计算耗时与基于Schnorr签名的适配器签名方案相当， 且均小于基于ECDSA 的适配器签名方案. 由于本文方案在验证预签名时要使用双线性配对， 双线性配对运算较其他运算耗时要多， 因此本文方案pVrfy 算法的计算耗时比基于Schnorr 签名的适配器签名方案多19.125 ms， 比基于ECDSA 的适配器签名方案多15.635 ms. 虽然与其他两个方案相比本文方案pVrfy 算法的计算效率最低， 然而本文的目标不是构造计算效率最优的适配器签名方案， 而是利用双线性配对构造方案以期望适配器签名技术可以与双线性配对结合， 在区块链系统中获得更为广泛的应用.

在存储开销方面， 比较以上三种方案的密钥长度、预签名长度与签名长度， 如表2 所示. 三种方案的密钥生成算法是相同的， 它们的私钥均为一个Z*q上的元素， 长度为32 字节， 公钥均为一个群G 上的元素，长度为64 字节， 所以密钥总长度为96 字节. 基于Schnorr 签名的适配器签名方案产生的预签名和签名均为两个Z*q上的元素， 长度为64 字节. 基于ECDSA 的适配器签名方案产生的预签名是四个Z*q上的元素和一个群G 上的元素， 总长度为192 字节; 产生的签名是两个Z*q上的元素， 长度为64 字节. 本文方案产生的预签名和签名均为一个Z*q上的元素加一个群G 上的元素， 长度为96 字节.

表2 存储开销对比(字节)Table 2 Storage overhead comparison (byte)

本文首次构造了一个基于双线性配对的适配器签名方案. 首先提出了一种基于双线性配对的数字签名方案Π. 基于计算Diffie-Hellman 困难问题假设， 利用随机预言机模型证明了该方案满足EUF-CMA. 然后在方案Π 的基础上， 构造了基于双线性配对的适配器签名方案ΞΠ并证明其满足aEUF-CMA， 预签名适配性和见证可提取性. 本文还将所设计方案的安全性和性能开销与文献中有代表性的适配器签名方案进行了全面比较. 下一步， 我们将研究在标准模型下可证明安全的双线性配对适配器签名方案， 并利用双线性配对的优良性质， 开发具有更多功能的适配器签名方案.

猜你喜欢 适配器数字签名挑战者 “挑战者”最后的绝唱小哥白尼(军事科学)(2022年3期)2022-06-09交通运输行业数字签名系统的设计与实现分析数码设计(2020年15期)2020-12-08图解英国挑战者-2主战坦克军事文摘(2020年2期)2020-03-10数字签名技术在计算机安全防护中的应用计算机与网络(2018年3期)2018-09-10关于电子商务中安全数字签名的研究课程教育研究·新教师教学(2015年18期)2017-09-27基于3D打印的轻型导弹适配器科学与财富(2017年24期)2017-09-06电源适配器怎么选电脑爱好者(2016年22期)2016-12-166款电力线网络适配器横向评测CHIP新电脑(2015年2期)2015-12-22美国麦格普公司新型M—LOK相机三脚架适配器轻兵器(2015年20期)2015-09-10掌握方法用好数字签名个人电脑(2014年12期)2014-12-29

推荐访问:配对 适配器 签名