随着量子计算机的高速发展，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 符号说明
符号说明M待签名消息checksum检查数seed一个长度为n位的随机种子n安全参数HM的哈希值H_hexH的16进制表示sk∕pk∕vk私钥∕公钥∕验证密钥
续表1
符号说明count_sb[i]每个16进制字符在H_hex中的个数sum_index[i]每个字母在H_hex中索引地址的和sub_iteration[i]每个字母从count_sb[i]中提取的特征iteration[i]每个字母从sum_index[i]中提取出的特征σM生成的签名sk_size∕pk_size私钥∕公钥的大小∕bσ_size签名的大小∕bsk[i]∕pk[i]∕vk[i]私钥∕公钥∕验证密钥中的元素fsk[i]∕fpk[i]∕fvk[i]私钥∕公钥∕验证密钥的第1部分bsk[i]∕bpk[i]∕bvk[i]私钥∕公钥∕验证密钥的第2部分fσ[i]∕bσ[i]σ的第1∕第2部分ADV试图破坏哈希函数的攻击者O一个签名预言机FOR一个试图破坏签名方案的伪造者MQFOR询问的消息σMQO返回的合理的MQ的签名(M',σM')FOR构造的合理的消息签名对how一个单向哈希函数ADVonewayness一个试图破坏how的单向性的攻击者
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
哈希函数输出长度经典安全性量子安全性第二原像攻击∕原像攻击碰撞攻击第二原像攻击∕原像攻击碰撞攻击SHA160160160808053SHA25625625612812885SHA384384384192192128SHA512512512256256171
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)；
③ for i=0 to 16 do /*生成私钥集合*/
④ sk.append(x)；
⑤ x←SHA512(x)；
⑥ end for
⑦ for i=0 to 15 do /*生成前16个公钥*/
⑧ fsk←SHA256(sk[i][0:31])；
⑨ bsk←SHA256(sk[i][32:63])；
for j=1 to 15 do
fsk←SHA256(fsk)；
fsk←fsk.Substrings(1,fsk.length-j*16); /*取字串*/
end for
fpk←SHA256(fsk)；
for j=1 to 128 do
bsk←SHA256(bsk)；
end for
bpk←bsk;
pk[i]←fpk‖bpk；
end for
fsk←sk[16][0:31]; /*第17个fsk*/
bsk←sk[16][32:63]; /*第17个bsk*/
for k=1 to 1921 do /*生成第17个公钥*/
fsk←SHA256(fsk)；
bsk←SHA256(bsk)；
end for
pk[16]=fsk‖bsk.
如算法1中行⑦～所示，本文用SHA256函数将前16个私钥元素fsk[i]分别哈希迭代17次，其中，第2次到第16次迭代过程加入取子串的操作，即取上1个哈希结果的子串作为当前哈希运算的输入值，生成对应的前16个长256 b的公钥元素fpk[i].如算法1的行～所示，本文将前16个bsk[i]元素分别哈希迭代129次，生成对应的前16个bpk[i].第17个fpk[16]和bpk[16]是通过fsk[16]和bsk[16]分别哈希迭代1 921次生成.每个公钥元素pk[i]由对应的fpk[i]和bpk[i]合并生成:
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’
③ for i=0 to 15 do
/*计算每个字母的个数和索引信息*/
④ sum_sb←0；
⑤ hsb←hex_symbols[i]；
⑥ index_sb←0；
⑦ for j=0 to 127 do
⑧ if H__hex[j]==hsb then
⑨ sum_sb←sum_sb+1；
index_sb←index_sb+j；
end if
end for
count_sb[i]←sum_sb;
/*计算每个字母个数*/
sum_index[i]←index_sb;
/*计算每个字母的索引地址*/
if count_sb[i]<=15 then
/*计算每个sub_ iteration[i]*/
sub_iteration[i]←count_sb[i]+1；
else
sub_iteration[i]←count_sb[i]//8；
end if
if count_sb[i]==0 then
/*计算每iteration[i] */
iteration[i]←1；
else
iteration[i]←sum_index[i]//cont_sb[i]；
end if
end for
for k=0 to 15 do
x←SHA256(sk[k][0:31])；
y←SHA256(sk[k][32:63])；
for j=1 to sub_iteration[k]-1 do
/*计算前16个Signature_one中元素*/
x←SHA256(x)；
x←x.Substrings(1,x.length-16*j)；
end for
fσ[k]←x；
Signature_one←Signature_one+x；
for j=1 to itertaion[k]-1 do
/*计算前16个Signature_two元素*/
y←SHA256(y)；
end for
bσ[k]←y；
Signature_two←Signature_two+y；
end for
checksum←0；
for j=0 to 15 do /*计算checksum*/
checksum←checksum+|count_sb[j]-8|；
end for
x←sk[16][0:31]；
y←sk[16][32:63]；
for j=1 to checksum do
/*计算第17个签名元素*/
x←SHA256(x)；
end for
fσ[16]←x；
Signature_one←Signature_one+fσ[16]；
for j=1 to 1920-checksum do
y←SHA256(y)；
end for
bσ[16]←y；
Signature_two←Signature_two+bσ[16].
前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)
第17个签名元素fσ[16]和bσ[16]是通过fsk[16]和bsk[16]分别哈希迭代checksum和1920-checksum次生成.生成的17个fσ[i]元素合并生成Signature_one，17个bσ[i]合并生成Signature_two.图2展示了消息“Hello World!”的签名构造过程.其中函数
表示从第2次到第i次的哈希运算加入了取子串操作.算法2展示了详细的签名构造过程.
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；
④ for i=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；
⑨ for j=1 to 16-sub_iteration[i] do
/*计算fvk[i]元素*/
x′←SHA256(x)；
x←x′.Substrings(1,x′.length-
(sub_iteratio n[i]-1+j)×16);
/*取子串操作*/
end for
for k=1 to 129-iteration[i] do
/*计算bvk[i]元素*/
y←SHA256(y)；
end for
fvk←SHA256(x)；
bvk←y；
vk[i]←fvk‖bvk；
end for
x←Signature_one.Substrings(lf,-1)；
y←Signature_two.Substrings(lb,-1)；
for i=1 to 1921-checksum do
x←SHA256(x)；
end for
for i=1 to checksum+1 do
y←SHA256(y)；
end for
vk[16]←x‖y；
for i=0 to 16 then
if vk[i]==pk[i]
output:Succeed;
else
output:Failed;
end if
end for
以下生成验证密钥.首先，验证者用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的签名；
⑦ if iterationMQ[α]<β then
⑧ Return fail;
⑨ else
构造消息MQ的签名；
When i≠α then
构造签名元素σMQ[i];
/*方法同SOTS*/
When i=α then {
end if
发送σMQ给伪造者F；
When F返回一个消息/签名对 (M′,σ′)
then {
if M′≠MQ且σ′是有效签名 then
if iterationM′[α]>β then
Return fail;
else
计算
Return x; /*ADVonewayness 成功*/
end if
end if }
其他所有情况Return fail;
end if
if α=16 then /*变换第17个公钥*/
随机选取β∈{1,2,…,1920};
F询问消息MQ的签名;
if checksumMQ<β then
Return fail;
else
构造消息MQ的签名；
When 0≤i≤15 then
构造签名元素σMQ [i]；
/*方法同SOTS*/
When i=α then {
end if
发送σMQ给伪造者F;
When F返回一个消息/签名对
(M′,σ′) then {
if M′≠MQ且σ′是有效签名 then
if checksumM′>β then
Return fail;
else
计算
Return x; /*ADVonewayness成功*/
end if
end if }
其他所有情况Return fail;
end if
如算法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]的尺寸和安全性
签名方案安全参数∕b消息哈希长度∕b哈希函数签名尺寸∕KB密钥尺寸∕KB后量子安全水平∕bLD-OTS512512SHA51232.8065.50171WOTS512512SHA5128.408.40171WOTS+384512SHA3846.307.10185NOTS512512SHA2561.001.00128SDS-OTS512512SHA5121.101.10164WOTS-S384384SHA3841.609.28128SOTS512512SHA2560.831.06128
可见，在保证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于分布式账本中，基于有向无环图设计一个抗量子的共识机制来提高分布式账本的安全性和性能.
[1]Jogenfors J. Quantum bitcoin: An anonymous, distributed, and secure currency secured by the no-cloning theorem of quantum mechanics[C] //Proc of 2019 IEEE Int Conf on Blockchain and Cryptocurrency(ICBC). Piscataway, NJ: IEEE, 2019: 245-252
[2]Merkle R C. A certified digital signature[C] //Proc of the Conf on the Theory and Application of Cryptology. Berlin: Springer, 1989: 218-238
[3]Hülsing A. W-OTS+—shorter signatures for hash-based signature schemes[C] //Proc of the Int Conf on Cryptology in Africa. Berlin: Springer, 2013: 173-188
[4]El Bansarkhani R, Geihs M, Buchmann J. Pqchain: Strategic design decisions for distributed ledger technologies against future threats[J]. IEEE Security & Privacy, 2018, 16(4): 57-65
[5]Shahid F, Khan A, Jeon G. Post-quantum distributed ledger for Internet of things[J]. Computers & Electrical Engineering, 2020, 83: No.106581
[6]Shahid F, Ahmad I, Imran M, et al. Novel one time signatures(NOTS): A compact post-quantum digital signature scheme[J]. IEEE Access, 2020, 8: 15895-15906
[7]Shahid F, Khan A. Smart digital signatures(SDS): A post-quantum digital signature scheme for distributed ledgers[J]. Future Generation Computer Systems, 2020, 111: 241-253
[8]Shahid F, Khan A, Malik S U R, et al. WOTS-S: A quantum secure compact signature scheme for distributed ledger[J]. Information Sciences, 2020, 539: 229-249
[9]Chalkias K, Brown J, Hearn M, et al. Blockchained post-quantum signatures[C] //Proc of 2018 IEEE Int Conf on Internet of Things(iThings) and IEEE Green Computing and Communications(GreenCom) and IEEE Cyber, Physical and Social Computing(CPSCom) and IEEE Smart Data(SmartData). Piscataway, NJ: IEEE, 2018: 1196-1203
