SOTS：一个基于哈希函数更短的后量子数字签名方案

卫宏儒 黄靖怡

(北京科技大学数理学院 北京 100083)

随着量子计算机的高速发展，Shor与Grover算法的出现，基于离散对数问题(discrete logarithm problem, DLP)、大整数分解问题(inter factorization problem, IFP)和椭圆曲线离散对数问题(elliptic curve discrete logarithm problem, ECDLP)的传统公钥签名算法将不安全.因此，可以抵抗量子计算机的后量子签名方案备受关注.基于哈希的签名方案是高效和可证明安全的.除此之外，与其他的基于格、基于编码、基于多变量的后量子签名方案相比，基于哈希函数的签名方案执行时间最少.因此，基于哈希函数的签名方案备受关注.然而，过大的密钥和签名尺寸限制了它在分布式账本和加密货币中的应用[1].

一个基于哈希函数的签名方案是由一个一次签名(one-time-signature, OTS)或一个多次签名(few-time-signature, FTS)方案，结合一个用于压缩和管理公钥的哈希树构成.其中，用于生成密钥和签名的OTS或FTS方案是基于哈希签名方案的核心.最初的OTS方案是由Lamport提出的LD-OTS方案.该方案逐位对消息进行签名，并对不同的待签名消息换用不同的密钥对.因此，对于一个长度为m位的消息进行签名，就需要m个签名和2m个密钥，如果一个签名长度为n位，则生成的签名和密钥长度分别为mn和2mn位，会消耗大量空间.WOTS方案[2]和它的变体方案WOTSPRF和WOTS+[3]都是在LD-OTS上进行了改进，将逐位签名替换为分组签名.其中WOTSPRF方案引入伪随机函数来替代抗碰撞(CR)哈希函数.WOTS+方案引入位掩码，将CR哈希函数替换为不可测单向函数(可以为一个哈希消息身份认证码，也可以为一个分组密码)来减少签名的数量和尺寸.但这些方案的签名和密钥的尺寸对于区块链等分布式账本来说还是过大.除此之外，运行效率低是WOTS+的问题.经过评估，WOTS+的密钥生成、签名生成和签名验证所需时间远高于WOTS.使用位掩码和随机操作，用不可测单向函数替代CR哈希函数比CR函数更加耗时.因此，使用CR哈希函数，通过其他方式降低空间的占用更佳.

椭圆曲线数字签名方案ECDSA是分布式账本最常用的数字签名方案.然而，ECDSA在后量子时代不是一个安全的签名方案.近几年，如IOTA，QRL，PQChain[4]和DL-for-IOT[5]等后量子分布式账本已经采用了基于哈希函数的数字签名方案.在这些分布式账本中应用的OTS方案主要是WOTS，WOTS+和WOTSPRF.因此，这些后量子分布式账本的不足之处包括了哈希签名方案密钥和签名尺寸过大的问题.

在近期文献[6-7]中提出的NOTS和SDS方案在WOTS的基础上，将对消息的签名转化为对16进制表示字符的签名，缩小了签名的个数.另一个新的方案WOTS-S[8]引入在哈希迭代中取子串的操作，减少了每个签名的长度.在这些WOTS变体方案的基础上，本文提出一个新的一次签名方案SOTS，在减少了密钥和签名长度的同时也提高了运行效率.

本文的主要贡献包括3个方面:

1) 提出了一种基于哈希函数的一次签名方案SOTS，通过对16进制字符进行签名和引入迭代取子串的过程，在减少签名个数的同时也缩短了每个签名的长度.相比于WOTS，SOTS在密钥和签名尺寸上分别缩小了77%和82%，相比于WOTS+，在密钥和签名尺寸上分别缩小了60.7%和60.5%;

2) 证明了在CPA模型和伪造者在一定时间内只能询问一条消息的情况下，SOTS方案是存在不可伪造的，它的安全性可规约为底层的单向哈希函数的安全性;

3) 通过实验，评估了新的签名方案，结果表明SOTS是一个高效的方案.与WOTS+相比，在密钥生成、签名生成和验证的时间上分别减少了71.4%，47.4%和60.9%.相比于WOTS-S，SOTS在运行效率上有明显提升.

1 基础知识

本节将介绍常用哈希函数的安全性以及攻击模型，这有利于后文对提出的签名方案的安全性分析.本文主要用到的符号及其说明在表1中给出.

Table 1 Symbols and Descriptions表1 符号说明

续表1

1.1 哈希函数的安全性

底层哈希函数的安全性是基于哈希函数数字签名方案最基本的安全性要求.一个安全的哈希函数可以抵抗原像攻击、第二原像攻击和碰撞攻击：

Pr(y←h(x);x′←ADV(y):x=x′)≤ε.

(1)

对于抗原像攻击，攻击者(ADV)不能或者以很小的概率能在已知像y的情况下推测出原像x：

Pr(y←h(x);x′←ADV(x,y):x≠x′∩y=h(x′))≤ε.

(2)

根据一个输入输出对(x,y)，攻击者很难找到另一个输入x′，使得输出也为y，这就是抗第二原像性.通过

Pr(x,x′←ADV:x≠x′∩h(x)=h(x′))≤ε

(3)

可知，抗碰撞攻击是指攻击者不能找到任意2个不同的输入x和x′，使得它们所成像相同.

一个哈希函数的安全水平是由它的输出长度n决定的.Grover算法和Shor算法降低了哈希函数的量子安全水平.表2给出了常用哈希函数的经典和量子安全水平.可见，一个n位的哈希函数可以提供n位和n/2位的经典安全水平来抵抗原像和碰撞攻击[9].然而，同样的哈希函数只能提供n/2位和n/3位的量子安全性来抵抗原像和碰撞攻击.

Table 2 Security of Hash Functions表2 哈希函数的安全性 b

1.2 选择明文攻击(CPA)模型

现存的很多研究，例如PQ-chain，compact PQ-chain等利用CPA模型来证明提出的数字签名方案的安全性.

CPA是一个攻击模型.在一定时间内，伪造者F选择消息，询问签名预言机O这些消息的签名，通过反馈得到的签名来构造一个合理的消息-签名(M′,σM′).完整的过程如图1所示.一个伪造者发送选择的消息集合(M1,M2,…,Mn)给O，O将对应的签名集合(σ1,σ2,…,σn)反馈给F.通过这些签名，F可以尝试构造一个新的消息-签名对(M′,σM′).如果该消息-签名对是合理的，即σM′是合理的并且M′没有在询问的消息集合中，则F成功.CPA-Secure-Model指F成功的概率很小可以忽略.

Fig.1 CPA model图1 CPA模型示意图

2 更短的一次签名SOTS

SOTS方案结合并提升了NOTS[5]和WOTS-S[7]方案，不仅减少了签名的个数，还缩小了每个签名的尺寸.本节将从密钥生成、签名生成和签名验证3个方面来详细阐述提出的新方案.

2.1 密钥生成

通过哈希函数SHA512，将随机生成的64 B的随机种子seed哈希迭代17次，每次生成一个私钥元素sk[i].私钥集合sk是由17个长512 b的私钥元素构成.

每个公钥元素由对应的私钥元素生成.在生成公钥之前，本文将每个私钥元素sk[i]均分为长256 b的前后2部分，分别记为fsk[i]和bsk[i].每个公钥元素的生成过程不同.详细的算法如算法1所示.

算法1.密钥生成算法.

输入：安全参数n=512；

输出：私钥集合sk[]、公钥集合pk[].

①seed←os.urandom(64);/*随机种子*/

②x←SHA512(seed)；

③ fori=0 to 16 do/*生成私钥集合*/

④sk.append(x)；

⑤x←SHA512(x)；

⑥ end for

⑦ fori=0 to 15 do/*生成前16个公钥*/

⑧fsk←SHA256(sk[i][0:31])；

⑨bsk←SHA256(sk[i][32:63])；

pk[i]=fpk[i]‖bpk[i],i=0→16.

公钥用于验证签名，因此公钥的设计要与签名的设计匹配.公钥元素生成所需的迭代次数也与签名过程有关.前16个签名元素所需哈希迭代次数的取值范围为[1,16]和[0,128]，因此前16个fpk[i]和bpk[i]元素分别由相应的私钥元素哈希迭代17和129次生成.第17个公钥元素用于验证检查数的签名，检查数对字符的个数进行检查，取值范围为[0,1 920]，因此fpk[16]和bpk[16]由相应的私钥通过哈希迭代1 921次生成.签名过程中决定哈希迭代次数函数的详细设计参见2.2节.

2.2 签名生成

在生成签名之前，本文先用SHA512函数计算待签名M消息的哈希值，并用16进制表示为H_hex.本文提取表示16进制字符(‘0’至‘f’)的每个字符在H_hex中的个数和所在的位置索引为特征.

本文用参数count_sb[i]表示16个字符在H_hex中的个数，因此该参数的取值一定在[0,128]范围内.显然，如果每个字符出现次数均等，则该值都应为8.参数sum_index[i]记录每个字符所在的索引地址之和.

(4)

(5)

在这2个参数的基础之上，计算出对应的sub_iteration[i]和iteration[i]来决定签名过程中哈希的迭代次数.

本文计算相应的检查数checksum为

(6)

构造签名的过程如算法2所示.

算法2.签名构造算法.

输入：待签名消息M、私钥集合sk[]；

输出：2部分签名Signature_one，Signature_two.

①H_hex←hexlify(SHA512(M));

/*十六进制*/

②hex_symbols←‘0123456789abcdef’

③ fori=0 to 15 do

/*计算每个字母的个数和索引信息*/

④sum_sb←0；

⑤hsb←hex_symbols[i]；

⑥index_sb←0；

⑦ forj=0 to 127 do

⑧ ifH__hex[j]==hsbthen

⑨sum_sb←sum_sb+1；

/*计算每个字母个数*/

/*计算每个字母的索引地址*/

/*计算每个sub_iteration[i]*/

/*计算每iteration[i] */

/*计算前16个Signature_one中元素*/

/*计算前16个Signature_two元素*/

/*计算第17个签名元素*/

前16个签名元素和第17个签名元素生成不同.前16个fσ[i]和bσ[i]元素分别是由对应的fsk[i]和bsk[i]元素通过哈希迭代sub_iteration[i]和iteration[i]次生成.但是这2种迭代过程不同.fσ[i]的生成过程与fpk[i]类似，都加入了迭代取子串的操作.其中，第2次到最后一次的哈希过程中，都进行了取子串操作.可见，因为sub_iteration[i]值的不同，生成的fσ[i]不是定长的256 b，而是变长的.每个fσ[i]的长度为

fσ[i].length=256- (sub_iteration[i]-1)×16,(i=0→15).

(7)

Fig. 2 Signature Creation of ‘Hello World!’图2 ‘Hello World!’签名生成过程

2.3 签名验证

与WOTS方案相同，验证密钥的生成只需要消息M和签名的信息即可.通过已知M的信息，验证者按照签名构造过程相同的方式计算相应的sub_iteration[i]，iteration[i]和checksum的值.接着，将fσ[i]和bσ[i]元素从签名信息Signature_one和Signature_two中提取出来，具体的提取过程如算法3中行④～⑧所示.

算法3.签名验证算法.

输入：待签名消息M，签名Signature_one，Signature_two，公钥集合pk[]；

输出：成功Succeed/失败Failed.

① 根据算法2中的步骤计算iteration[],sub_iteration[]和checksum.

②lf←1；

③lb←1；

④ fori=0 to 15 do

/*前16个验证公钥元素*/

⑤x←Signature_one.Substrings(lf,lf+256-(sub_iteration[i]-1)×16);

/* 提取每个fσ[i]元素*/

⑥lf←lf+256-(sub_iteration[i]-1)×16；

⑦y←Signature_two.Substrings(lb,lb+256)；

⑧lb←lb+256；

⑨ forj=1 to 16-sub_iteration[i] do

/*计算fvk[i]元素*/

(sub_iteration[i]-1+j)×16);

/*取子串操作*/

/*计算bvk[i]元素*/

以下生成验证密钥.首先，验证者用SHA256函数分别对前16个fσ[i]和bσ[i]元素迭代16-sub_iteration[i]和129-iteration[i]次，生成对应的前16个fvk[i]和bvk[i]值.其中，如算法3中行⑨～所示，在生成fvk[i]的过程中，采用了取子串的操作，每个哈希输入值由sub_iteration[i]决定.式(8)展示了所选取子串的长度.如算法3中行～所示，第17个验证密钥元素fvk[16]和bvk[16]是由对应的fσ[16]和bσ[16]哈希迭代1921-checksum和checksum+1次生成.每个验证密钥元素vk[i]由对应的fvk[i]与bvk[i]合并构成.

x=x′.Substrings(1,x′.length- (sub_iteration[i]-1+j)×16),j=1→16-sub_iteration[i].

(8)

如果每个公钥元素pk[i]与对应的验证密钥元素vk[i]相等，则验证成功.算法3展示了详细的签名验证过程.

3 安全性分析

本节将证明SOTS的存在不可伪造性.

3.1 存在不可伪造性

在第1.2节中介绍的CPA模型的基础上，本节将阐述SOTS的存在不可伪造性定义.本文先假设伪造者F的能力.假设F只知道公钥pk，并且只能询问一个消息的签名.

定义1[6].SOTS的存在不可伪造性定义为：在签名预言机(O)知道新的密钥对(sk,pk)，伪造者F只知道公钥pk的前提下，伪造者F向O询问一个消息MQ的合理签名.当接收到来自O返回的签名σMQ，F试图返回一个新的合理的消息-签名对(M′,σM′)，即需要满足σM′是合理的，并且MQ≠M′的条件.如果在时间t内，F成功返回消息-签名对的概率不大于ε，则就说SOTS在CPA模型下是存在不可伪造的，记为(t,ε,1)-EU.

3.2 SOTS的安全性证明

本节将证明只要底层哈希函数是一个单向哈希函数，SOTS在CPA模型下就是存在不可伪造的，即证明SOTS的安全性可规约为底层哈希函数的安全性.算法4阐述了一个攻击者ADVonewayness利用F去攻击所用的单向哈希函数how.在这个过程中，ADVonewayness扮演签名预言机O的角色.

算法4.攻击函数的单向性.

输入：单向哈希函数how，SOTS签名算法、安全参数n、伪造者F、像y；

输出：y的前像x，使得y=how(x).

① 生成一个新的SOTS密钥对(sk,pk)；

② 随机选取α∈{0,1,…,16};

/*选择y信息放入的公钥*/

③ if 0≤α≤15 then

④ 随机选取β∈{1,2,…,128};

⑥ 伪造者F询问消息MQ的签名；

⑦ ifiterationMQ[α]<βthen

⑧ Return fail;

⑨ else

构造签名元素σMQ[i];

/*方法同SOTS*/

then {

构造签名元素σMQ[i]；

/*方法同SOTS*/

(M′,σ′) then {

如算法4中行①～②可见，攻击者构造一个新的密钥对(sk,pk)，随机从0～16中选择一个数α来决定放入y的信息的公钥元素.根据第2节中SOTS的构造方法可见，第17个公钥元素的构造与前16个公钥元素的构造不同，第17个签名的生成方法也与前16个不同，因此，这节将分为2种情况讨论.

第1种情况是0≤α≤15.本文参考文献[6]中的方法来证明提出的方案的安全性.ADVonewayness随机生成一个取值在[0,128]范围内的数β，将y用哈希函数how迭代129-β次，将结果作为第α+1个公钥元素bpk[α].随后，运行F.当F询问一个消息MQ，如果该消息的iteration[α]值满足算法4中⑦的条件，则攻击失败并退出.否则，ADVonewayness将按照算法4中行～的方式构造合理的签名σMQ，反馈给F.如果F构造的消息-签名对(M′,σM′)没有满足算法4中行的条件，则y的前像x可以从σM′中推测出来，使得how(x)=y.x具体的计算方式如算法4的行所示.

可见，只有ADVonewayness成功的构造消息MQ的签名，F成功返回一个消息-签名对(M′,σM′)，并且x可以从(M′,σM′)中推测出来，攻击才是成功的.式(9)说明了满足0≤α≤15并且攻击成功的概率.因此，最大的成功概率为0.0074εF，即Pr(ADVonewayness)≤0.0074εF.式(10)计算了攻击过程需要的总时间.式(11)和(12)展示了参数tFOR_SOTS和εSOTS的取值，因此，在CPA模型和(tFOR_SOTS,εSOTS,1)参数下，SOTS是存在不可伪造的，记为：(tFOR_SOTS,εSOTS,1)-EU-CPA.即，ADVonewayness在时间tFOR_SOTS内成功返回一个合理消息-签名对(M′,σM′)的概率不超过εSOTS.这也能看出该方案的安全性可规约为底层哈希函数的单向性.

(9)

tADVonewayness=tKey_Generation+tSignσM+tFOR_SOTS,

(10)

tFOR_SOTS=tADVonewayness-tKey_Generation-tsignσM,

(11)

(12)

第2种情况是：α=16，即变换第17个公钥值.所用的初始密钥对同第1种情况.首先，ADVonewayness随机选取一个范围为[1,1920]的整数β，将y哈希迭代1921-β次，生成新的公钥元素fpk[α].随后，攻击的步骤与第一种情况相同.算法4中行～详细阐述了该情况下的攻击过程和需要满足的条件.式(10)、式(13)计算了攻击所用的时间和成功的概率.可见，成功的概率不超过0.000 03εF.同理，在这种情况下，SOTS是存在不可伪造的，即(tFOR_SOTS,εSOTS,1)-EU-CPA.

(13)

因此，SOTS在CPA模型和伪造者的假设条件下是存在不可伪造的.它的安全性可规约为底层所用哈希函数的单向性.

4 密钥和签名尺寸

本节将计算SOTS的密钥和签名大小，并与其他的WOTS变体方案比较.

4.1 SOTS密钥和签名尺寸

通过第2节对签名方案的阐述，密钥和签名尺寸是可以计算的.17个私钥元素是一个随机种子seed通过哈希函数SHA512迭代生成，17个公钥元素是通过对应的私钥生成，则它们的尺寸为

pk_size=sk_size=|sk|×512=|pk|×512= 17×512=1.06 KB.

由算法2可见，每个签名元素都是由对应私钥元素通过SHA256哈希函数迭代生成.在fσ[i]生成过程中，进行了取子串操作，而迭代的次数和取子串的长度由十六进制字符在消息哈希中的特征决定.因此，由于每个字符的数量不同，哈希函数迭代的次数和生成的签名长度是不固定的.从式(7)可以看出，最长和最短的fσ[i]元素的长度分别是16 b和256 b.因此，由17个fσ[i]元素合并生成的Signature_one的长度也是变化的.每个bσ[i]的长度为256 b，因此，Signature_two的长度是固定的.因此，SOTS的签名尺寸最小为0.59 KB，最大为1.06 KB，平均长度为0.83 KB.

4.2 评 估

SOTS是一个基于WOTS改进的签名方案，可以提供更小的密钥和签名尺寸.表3将SOTS与其他WOTS变体方案进行对比.

Table 3 Sizes and Security: OTS Schemes[6-8]表3 OTS方案[6-8]的尺寸和安全性

可见，在保证128 b的后量子安全水平下，在签名尺寸上，相比于WOTS和WOTS+分别减小了90.1%和86.8%.与最近提出的NOTS,SDS-OTS和WOTS-S方案相比，在签名尺寸上，分别减少了17%，24.5%和48.1%.SOTS相比于WOTS和WOTS+，在密钥尺寸上，分别减少了87.4%和85.1%.

在保证相同的128 b的后量子安全级别下，WOTS的密钥和签名尺寸都为4.6 KB，WOTS+的密钥和签名尺寸分别为2.7 KB和2.1 KB.因此，在128 b后量子安全水平下，相比于WOTS，在签名和密钥尺寸上分别减少了82%和77%.相比于WOTS+，在签名和密钥尺寸上分别减少了60.5%和60.7%.

5 运行效率评估

为了评估SOTS运行的效率，即时间，本文将SOTS与LD-OTS,WOTS,WOTS+,NOTS,SDS-OTS,WOTS-S方案进行对比.图3～5是在Intel Core i7-8650U CPU(2.1 GHz)处理器，16 GB RAM的“JetBrains PyCharm Community Edition 2019.2 EAP”环境中运行Windows 10 x64系统，并使用python语言编译得到的结果.图3～5分别展示了这7个签名方案在表3的参数下，生成密钥、构造签名和验证签名所需要的时间.

Fig. 3 Key generation time of the OTS schemes图3 OTS方案生成密钥的时间

Fig. 4 Signature creation time of the OTS schemes图4 OTS方案构造签名的时间

Fig. 5 Signature verification time of the OTS schemes图5 OTS方案验证签名的时间

由结果可见，WOTS+方案运行效率很低.与WOTS+相比，SOTS在生成密钥、构造签名和验证签名的时间上，分别减少了71.4%,47.7%和60.9%.与WOTS方案相比，SOTS以增加很短的运行时间为代价，大量减少了空间上的占用.SOTS与NOTS,SDS-OTS方案的运行效率相差甚小.相比于WOTS-S,SOTS在签名和验证时间上有明显减少.

6 总结和展望

在CPA模型下，SOTS数字签名方案是存在不可伪造地高效的WOTS变体方案.在相同128 b后量子安全级别下，与WOTS相比，SOTS在密钥和签名尺寸上分别减少了77%和82%.与WOTS+相比，SOTS在密钥和签名上分别减少了60.7%和60.5%.除此之外，SOTS运行效率高.与WOTS+相比，在生成密钥、构造签名和验证签名的时间上分别减少了71.4%，47.7%和60.9%.在未来的研究中，我们将应用SOTS于分布式账本中，基于有向无环图设计一个抗量子的共识机制来提高分布式账本的安全性和性能.