衛(wèi)宏儒 黃靖怡

(北京科技大學(xué)數(shù)理學(xué)院 北京 100083)

隨著量子計(jì)算機(jī)的高速發(fā)展，Shor與Grover算法的出現(xiàn)，基于離散對數(shù)問題(discrete logarithm problem, DLP)、大整數(shù)分解問題(inter factorization problem, IFP)和橢圓曲線離散對數(shù)問題(elliptic curve discrete logarithm problem, ECDLP)的傳統(tǒng)公鑰簽名算法將不安全.因此，可以抵抗量子計(jì)算機(jī)的后量子簽名方案備受關(guān)注.基于哈希的簽名方案是高效和可證明安全的.除此之外，與其他的基于格、基于編碼、基于多變量的后量子簽名方案相比，基于哈希函數(shù)的簽名方案執(zhí)行時(shí)間最少.因此，基于哈希函數(shù)的簽名方案備受關(guān)注.然而，過大的密鑰和簽名尺寸限制了它在分布式賬本和加密貨幣中的應(yīng)用[1].

一個(gè)基于哈希函數(shù)的簽名方案是由一個(gè)一次簽名(one-time-signature, OTS)或一個(gè)多次簽名(few-time-signature, FTS)方案，結(jié)合一個(gè)用于壓縮和管理公鑰的哈希樹構(gòu)成.其中，用于生成密鑰和簽名的OTS或FTS方案是基于哈希簽名方案的核心.最初的OTS方案是由Lamport提出的LD-OTS方案.該方案逐位對消息進(jìn)行簽名，并對不同的待簽名消息換用不同的密鑰對.因此，對于一個(gè)長度為m位的消息進(jìn)行簽名，就需要m個(gè)簽名和2m個(gè)密鑰，如果一個(gè)簽名長度為n位，則生成的簽名和密鑰長度分別為mn和2mn位，會(huì)消耗大量空間.WOTS方案[2]和它的變體方案WOTSPRF和WOTS+[3]都是在LD-OTS上進(jìn)行了改進(jìn)，將逐位簽名替換為分組簽名.其中WOTSPRF方案引入偽隨機(jī)函數(shù)來替代抗碰撞(CR)哈希函數(shù).WOTS+方案引入位掩碼，將CR哈希函數(shù)替換為不可測單向函數(shù)(可以為一個(gè)哈希消息身份認(rèn)證碼，也可以為一個(gè)分組密碼)來減少簽名的數(shù)量和尺寸.但這些方案的簽名和密鑰的尺寸對于區(qū)塊鏈等分布式賬本來說還是過大.除此之外，運(yùn)行效率低是WOTS+的問題.經(jīng)過評估，WOTS+的密鑰生成、簽名生成和簽名驗(yàn)證所需時(shí)間遠(yuǎn)高于WOTS.使用位掩碼和隨機(jī)操作，用不可測單向函數(shù)替代CR哈希函數(shù)比CR函數(shù)更加耗時(shí).因此，使用CR哈希函數(shù)，通過其他方式降低空間的占用更佳.

橢圓曲線數(shù)字簽名方案ECDSA是分布式賬本最常用的數(shù)字簽名方案.然而，ECDSA在后量子時(shí)代不是一個(gè)安全的簽名方案.近幾年，如IOTA，QRL，PQChain[4]和DL-for-IOT[5]等后量子分布式賬本已經(jīng)采用了基于哈希函數(shù)的數(shù)字簽名方案.在這些分布式賬本中應(yīng)用的OTS方案主要是WOTS，WOTS+和WOTSPRF.因此，這些后量子分布式賬本的不足之處包括了哈希簽名方案密鑰和簽名尺寸過大的問題.

在近期文獻(xiàn)[6-7]中提出的NOTS和SDS方案在WOTS的基礎(chǔ)上，將對消息的簽名轉(zhuǎn)化為對16進(jìn)制表示字符的簽名，縮小了簽名的個(gè)數(shù).另一個(gè)新的方案WOTS-S[8]引入在哈希迭代中取子串的操作，減少了每個(gè)簽名的長度.在這些WOTS變體方案的基礎(chǔ)上，本文提出一個(gè)新的一次簽名方案SOTS，在減少了密鑰和簽名長度的同時(shí)也提高了運(yùn)行效率.

本文的主要貢獻(xiàn)包括3個(gè)方面:

1) 提出了一種基于哈希函數(shù)的一次簽名方案SOTS，通過對16進(jìn)制字符進(jìn)行簽名和引入迭代取子串的過程，在減少簽名個(gè)數(shù)的同時(shí)也縮短了每個(gè)簽名的長度.相比于WOTS，SOTS在密鑰和簽名尺寸上分別縮小了77%和82%，相比于WOTS+，在密鑰和簽名尺寸上分別縮小了60.7%和60.5%;

2) 證明了在CPA模型和偽造者在一定時(shí)間內(nèi)只能詢問一條消息的情況下，SOTS方案是存在不可偽造的，它的安全性可規(guī)約為底層的單向哈希函數(shù)的安全性;

3) 通過實(shí)驗(yàn)，評估了新的簽名方案，結(jié)果表明SOTS是一個(gè)高效的方案.與WOTS+相比，在密鑰生成、簽名生成和驗(yàn)證的時(shí)間上分別減少了71.4%，47.4%和60.9%.相比于WOTS-S，SOTS在運(yùn)行效率上有明顯提升.

1 基礎(chǔ)知識

本節(jié)將介紹常用哈希函數(shù)的安全性以及攻擊模型，這有利于后文對提出的簽名方案的安全性分析.本文主要用到的符號及其說明在表1中給出.

Table 1 Symbols and Descriptions表1 符號說明

續(xù)表1

1.1 哈希函數(shù)的安全性

底層哈希函數(shù)的安全性是基于哈希函數(shù)數(shù)字簽名方案最基本的安全性要求.一個(gè)安全的哈希函數(shù)可以抵抗原像攻擊、第二原像攻擊和碰撞攻擊：

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)

根據(jù)一個(gè)輸入輸出對(x,y)，攻擊者很難找到另一個(gè)輸入x′，使得輸出也為y，這就是抗第二原像性.通過

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

(3)

可知，抗碰撞攻擊是指攻擊者不能找到任意2個(gè)不同的輸入x和x′，使得它們所成像相同.

一個(gè)哈希函數(shù)的安全水平是由它的輸出長度n決定的.Grover算法和Shor算法降低了哈希函數(shù)的量子安全水平.表2給出了常用哈希函數(shù)的經(jīng)典和量子安全水平.可見，一個(gè)n位的哈希函數(shù)可以提供n位和n/2位的經(jīng)典安全水平來抵抗原像和碰撞攻擊[9].然而，同樣的哈希函數(shù)只能提供n/2位和n/3位的量子安全性來抵抗原像和碰撞攻擊.

Table 2 Security of Hash Functions表2 哈希函數(shù)的安全性 b

1.2 選擇明文攻擊(CPA)模型

現(xiàn)存的很多研究，例如PQ-chain，compact PQ-chain等利用CPA模型來證明提出的數(shù)字簽名方案的安全性.

CPA是一個(gè)攻擊模型.在一定時(shí)間內(nèi)，偽造者F選擇消息，詢問簽名預(yù)言機(jī)O這些消息的簽名，通過反饋得到的簽名來構(gòu)造一個(gè)合理的消息-簽名(M′,σM′).完整的過程如圖1所示.一個(gè)偽造者發(fā)送選擇的消息集合(M1,M2,…,Mn)給O，O將對應(yīng)的簽名集合(σ1,σ2,…,σn)反饋給F.通過這些簽名，F(xiàn)可以嘗試構(gòu)造一個(gè)新的消息-簽名對(M′,σM′).如果該消息-簽名對是合理的，即σM′是合理的并且M′沒有在詢問的消息集合中，則F成功.CPA-Secure-Model指F成功的概率很小可以忽略.

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

2 更短的一次簽名SOTS

SOTS方案結(jié)合并提升了NOTS[5]和WOTS-S[7]方案，不僅減少了簽名的個(gè)數(shù)，還縮小了每個(gè)簽名的尺寸.本節(jié)將從密鑰生成、簽名生成和簽名驗(yàn)證3個(gè)方面來詳細(xì)闡述提出的新方案.

2.1 密鑰生成

通過哈希函數(shù)SHA512，將隨機(jī)生成的64 B的隨機(jī)種子seed哈希迭代17次，每次生成一個(gè)私鑰元素sk[i].私鑰集合sk是由17個(gè)長512 b的私鑰元素構(gòu)成.

每個(gè)公鑰元素由對應(yīng)的私鑰元素生成.在生成公鑰之前，本文將每個(gè)私鑰元素sk[i]均分為長256 b的前后2部分，分別記為fsk[i]和bsk[i].每個(gè)公鑰元素的生成過程不同.詳細(xì)的算法如算法1所示.

算法1.密鑰生成算法.

輸入：安全參數(shù)n=512；

輸出：私鑰集合sk[]、公鑰集合pk[].

①seed←os.urandom(64);/*隨機(jī)種子*/

②x←SHA512(seed)；

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

④sk.append(x)；

⑤x←SHA512(x)；

⑥ end for

⑦ fori=0 to 15 do/*生成前16個(gè)公鑰*/

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

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

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

公鑰用于驗(yàn)證簽名，因此公鑰的設(shè)計(jì)要與簽名的設(shè)計(jì)匹配.公鑰元素生成所需的迭代次數(shù)也與簽名過程有關(guān).前16個(gè)簽名元素所需哈希迭代次數(shù)的取值范圍為[1,16]和[0,128]，因此前16個(gè)fpk[i]和bpk[i]元素分別由相應(yīng)的私鑰元素哈希迭代17和129次生成.第17個(gè)公鑰元素用于驗(yàn)證檢查數(shù)的簽名，檢查數(shù)對字符的個(gè)數(shù)進(jìn)行檢查，取值范圍為[0,1 920]，因此fpk[16]和bpk[16]由相應(yīng)的私鑰通過哈希迭代1 921次生成.簽名過程中決定哈希迭代次數(shù)函數(shù)的詳細(xì)設(shè)計(jì)參見2.2節(jié).

2.2 簽名生成

在生成簽名之前，本文先用SHA512函數(shù)計(jì)算待簽名M消息的哈希值，并用16進(jìn)制表示為H_hex.本文提取表示16進(jìn)制字符(‘0’至‘f’)的每個(gè)字符在H_hex中的個(gè)數(shù)和所在的位置索引為特征.

本文用參數(shù)count_sb[i]表示16個(gè)字符在H_hex中的個(gè)數(shù)，因此該參數(shù)的取值一定在[0,128]范圍內(nèi).顯然，如果每個(gè)字符出現(xiàn)次數(shù)均等，則該值都應(yīng)為8.參數(shù)sum_index[i]記錄每個(gè)字符所在的索引地址之和.

(4)

(5)

在這2個(gè)參數(shù)的基礎(chǔ)之上，計(jì)算出對應(yīng)的sub_iteration[i]和iteration[i]來決定簽名過程中哈希的迭代次數(shù).

本文計(jì)算相應(yīng)的檢查數(shù)checksum為

(6)

構(gòu)造簽名的過程如算法2所示.

算法2.簽名構(gòu)造算法.

輸入：待簽名消息M、私鑰集合sk[]；

輸出：2部分簽名Signature_one，Signature_two.

①H_hex←hexlify(SHA512(M));

/*十六進(jìn)制*/

②hex_symbols←‘0123456789abcdef’

③ fori=0 to 15 do

/*計(jì)算每個(gè)字母的個(gè)數(shù)和索引信息*/

④sum_sb←0；

⑤hsb←hex_symbols[i]；

⑥index_sb←0；

⑦ forj=0 to 127 do

⑧ ifH__hex[j]==hsbthen

⑨sum_sb←sum_sb+1；

/*計(jì)算每個(gè)字母個(gè)數(shù)*/

/*計(jì)算每個(gè)字母的索引地址*/

/*計(jì)算每個(gè)sub_iteration[i]*/

/*計(jì)算每iteration[i] */

/*計(jì)算前16個(gè)Signature_one中元素*/

/*計(jì)算前16個(gè)Signature_two元素*/

/*計(jì)算第17個(gè)簽名元素*/

前16個(gè)簽名元素和第17個(gè)簽名元素生成不同.前16個(gè)fσ[i]和bσ[i]元素分別是由對應(yīng)的fsk[i]和bsk[i]元素通過哈希迭代sub_iteration[i]和iteration[i]次生成.但是這2種迭代過程不同.fσ[i]的生成過程與fpk[i]類似，都加入了迭代取子串的操作.其中，第2次到最后一次的哈希過程中，都進(jìn)行了取子串操作.可見，因?yàn)閟ub_iteration[i]值的不同，生成的fσ[i]不是定長的256 b，而是變長的.每個(gè)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 簽名驗(yàn)證

與WOTS方案相同，驗(yàn)證密鑰的生成只需要消息M和簽名的信息即可.通過已知M的信息，驗(yàn)證者按照簽名構(gòu)造過程相同的方式計(jì)算相應(yīng)的sub_iteration[i]，iteration[i]和checksum的值.接著，將fσ[i]和bσ[i]元素從簽名信息Signature_one和Signature_two中提取出來，具體的提取過程如算法3中行④～⑧所示.

算法3.簽名驗(yàn)證算法.

輸入：待簽名消息M，簽名Signature_one，Signature_two，公鑰集合pk[]；

輸出：成功Succeed/失敗Failed.

① 根據(jù)算法2中的步驟計(jì)算iteration[],sub_iteration[]和checksum.

②lf←1；

③lb←1；

④ fori=0 to 15 do

/*前16個(gè)驗(yàn)證公鑰元素*/

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

/* 提取每個(gè)fσ[i]元素*/

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

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

⑧l(xiāng)b←lb+256；

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

/*計(jì)算fvk[i]元素*/

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

/*取子串操作*/

/*計(jì)算bvk[i]元素*/

以下生成驗(yàn)證密鑰.首先，驗(yàn)證者用SHA256函數(shù)分別對前16個(gè)fσ[i]和bσ[i]元素迭代16-sub_iteration[i]和129-iteration[i]次，生成對應(yīng)的前16個(gè)fvk[i]和bvk[i]值.其中，如算法3中行⑨～所示，在生成fvk[i]的過程中，采用了取子串的操作，每個(gè)哈希輸入值由sub_iteration[i]決定.式(8)展示了所選取子串的長度.如算法3中行～所示，第17個(gè)驗(yàn)證密鑰元素fvk[16]和bvk[16]是由對應(yīng)的fσ[16]和bσ[16]哈希迭代1921-checksum和checksum+1次生成.每個(gè)驗(yàn)證密鑰元素vk[i]由對應(yīng)的fvk[i]與bvk[i]合并構(gòu)成.

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

(8)

如果每個(gè)公鑰元素pk[i]與對應(yīng)的驗(yàn)證密鑰元素vk[i]相等，則驗(yàn)證成功.算法3展示了詳細(xì)的簽名驗(yàn)證過程.

3 安全性分析

本節(jié)將證明SOTS的存在不可偽造性.

3.1 存在不可偽造性

在第1.2節(jié)中介紹的CPA模型的基礎(chǔ)上，本節(jié)將闡述SOTS的存在不可偽造性定義.本文先假設(shè)偽造者F的能力.假設(shè)F只知道公鑰pk，并且只能詢問一個(gè)消息的簽名.

定義1[6].SOTS的存在不可偽造性定義為：在簽名預(yù)言機(jī)(O)知道新的密鑰對(sk,pk)，偽造者F只知道公鑰pk的前提下，偽造者F向O詢問一個(gè)消息MQ的合理簽名.當(dāng)接收到來自O(shè)返回的簽名σMQ，F(xiàn)試圖返回一個(gè)新的合理的消息-簽名對(M′,σM′)，即需要滿足σM′是合理的，并且MQ≠M(fèi)′的條件.如果在時(shí)間t內(nèi)，F(xiàn)成功返回消息-簽名對的概率不大于ε，則就說SOTS在CPA模型下是存在不可偽造的，記為(t,ε,1)-EU.

3.2 SOTS的安全性證明

本節(jié)將證明只要底層哈希函數(shù)是一個(gè)單向哈希函數(shù)，SOTS在CPA模型下就是存在不可偽造的，即證明SOTS的安全性可規(guī)約為底層哈希函數(shù)的安全性.算法4闡述了一個(gè)攻擊者ADVonewayness利用F去攻擊所用的單向哈希函數(shù)how.在這個(gè)過程中，ADVonewayness扮演簽名預(yù)言機(jī)O的角色.

算法4.攻擊函數(shù)的單向性.

輸入：單向哈希函數(shù)how，SOTS簽名算法、安全參數(shù)n、偽造者F、像y；

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

① 生成一個(gè)新的SOTS密鑰對(sk,pk)；

② 隨機(jī)選取α∈{0,1,…,16};

/*選擇y信息放入的公鑰*/

③ if 0≤α≤15 then

④ 隨機(jī)選取β∈{1,2,…,128};

⑥ 偽造者F詢問消息MQ的簽名；

⑦ ifiterationMQ[α]<βthen

⑧ Return fail;

⑨ else

構(gòu)造簽名元素σMQ[i];

/*方法同SOTS*/

then {

構(gòu)造簽名元素σMQ[i]；

/*方法同SOTS*/

(M′,σ′) then {

如算法4中行①～②可見，攻擊者構(gòu)造一個(gè)新的密鑰對(sk,pk)，隨機(jī)從0～16中選擇一個(gè)數(shù)α來決定放入y的信息的公鑰元素.根據(jù)第2節(jié)中SOTS的構(gòu)造方法可見，第17個(gè)公鑰元素的構(gòu)造與前16個(gè)公鑰元素的構(gòu)造不同，第17個(gè)簽名的生成方法也與前16個(gè)不同，因此，這節(jié)將分為2種情況討論.

第1種情況是0≤α≤15.本文參考文獻(xiàn)[6]中的方法來證明提出的方案的安全性.ADVonewayness隨機(jī)生成一個(gè)取值在[0,128]范圍內(nèi)的數(shù)β，將y用哈希函數(shù)how迭代129-β次，將結(jié)果作為第α+1個(gè)公鑰元素bpk[α].隨后，運(yùn)行F.當(dāng)F詢問一個(gè)消息MQ，如果該消息的iteration[α]值滿足算法4中⑦的條件，則攻擊失敗并退出.否則，ADVonewayness將按照算法4中行～的方式構(gòu)造合理的簽名σMQ，反饋給F.如果F構(gòu)造的消息-簽名對(M′,σM′)沒有滿足算法4中行的條件，則y的前像x可以從σM′中推測出來，使得how(x)=y.x具體的計(jì)算方式如算法4的行所示.

可見，只有ADVonewayness成功的構(gòu)造消息MQ的簽名，F(xiàn)成功返回一個(gè)消息-簽名對(M′,σM′)，并且x可以從(M′,σM′)中推測出來，攻擊才是成功的.式(9)說明了滿足0≤α≤15并且攻擊成功的概率.因此，最大的成功概率為0.0074εF，即Pr(ADVonewayness)≤0.0074εF.式(10)計(jì)算了攻擊過程需要的總時(shí)間.式(11)和(12)展示了參數(shù)tFOR_SOTS和εSOTS的取值，因此，在CPA模型和(tFOR_SOTS,εSOTS,1)參數(shù)下，SOTS是存在不可偽造的，記為：(tFOR_SOTS,εSOTS,1)-EU-CPA.即，ADVonewayness在時(shí)間tFOR_SOTS內(nèi)成功返回一個(gè)合理消息-簽名對(M′,σM′)的概率不超過εSOTS.這也能看出該方案的安全性可規(guī)約為底層哈希函數(shù)的單向性.

(9)

tADVonewayness=tKey_Generation+tSignσM+tFOR_SOTS,

(10)

tFOR_SOTS=tADVonewayness-tKey_Generation-tsignσM,

(11)

(12)

第2種情況是：α=16，即變換第17個(gè)公鑰值.所用的初始密鑰對同第1種情況.首先，ADVonewayness隨機(jī)選取一個(gè)范圍為[1,1920]的整數(shù)β，將y哈希迭代1921-β次，生成新的公鑰元素fpk[α].隨后，攻擊的步驟與第一種情況相同.算法4中行～詳細(xì)闡述了該情況下的攻擊過程和需要滿足的條件.式(10)、式(13)計(jì)算了攻擊所用的時(shí)間和成功的概率.可見，成功的概率不超過0.000 03εF.同理，在這種情況下，SOTS是存在不可偽造的，即(tFOR_SOTS,εSOTS,1)-EU-CPA.

(13)

因此，SOTS在CPA模型和偽造者的假設(shè)條件下是存在不可偽造的.它的安全性可規(guī)約為底層所用哈希函數(shù)的單向性.

4 密鑰和簽名尺寸

本節(jié)將計(jì)算SOTS的密鑰和簽名大小，并與其他的WOTS變體方案比較.

4.1 SOTS密鑰和簽名尺寸

通過第2節(jié)對簽名方案的闡述，密鑰和簽名尺寸是可以計(jì)算的.17個(gè)私鑰元素是一個(gè)隨機(jī)種子seed通過哈希函數(shù)SHA512迭代生成，17個(gè)公鑰元素是通過對應(yīng)的私鑰生成，則它們的尺寸為

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

由算法2可見，每個(gè)簽名元素都是由對應(yīng)私鑰元素通過SHA256哈希函數(shù)迭代生成.在fσ[i]生成過程中，進(jìn)行了取子串操作，而迭代的次數(shù)和取子串的長度由十六進(jìn)制字符在消息哈希中的特征決定.因此，由于每個(gè)字符的數(shù)量不同，哈希函數(shù)迭代的次數(shù)和生成的簽名長度是不固定的.從式(7)可以看出，最長和最短的fσ[i]元素的長度分別是16 b和256 b.因此，由17個(gè)fσ[i]元素合并生成的Signature_one的長度也是變化的.每個(gè)bσ[i]的長度為256 b，因此，Signature_two的長度是固定的.因此，SOTS的簽名尺寸最小為0.59 KB，最大為1.06 KB，平均長度為0.83 KB.

4.2 評 估

SOTS是一個(gè)基于WOTS改進(jìn)的簽名方案，可以提供更小的密鑰和簽名尺寸.表3將SOTS與其他WOTS變體方案進(jìn)行對比.

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 運(yùn)行效率評估

為了評估SOTS運(yùn)行的效率，即時(shí)間，本文將SOTS與LD-OTS,WOTS,WOTS+,NOTS,SDS-OTS,WOTS-S方案進(jìn)行對比.圖3～5是在Intel Core i7-8650U CPU(2.1 GHz)處理器，16 GB RAM的“JetBrains PyCharm Community Edition 2019.2 EAP”環(huán)境中運(yùn)行Windows 10 x64系統(tǒng)，并使用python語言編譯得到的結(jié)果.圖3～5分別展示了這7個(gè)簽名方案在表3的參數(shù)下，生成密鑰、構(gòu)造簽名和驗(yàn)證簽名所需要的時(shí)間.

Fig. 3 Key generation time of the OTS schemes圖3 OTS方案生成密鑰的時(shí)間

Fig. 4 Signature creation time of the OTS schemes圖4 OTS方案構(gòu)造簽名的時(shí)間

Fig. 5 Signature verification time of the OTS schemes圖5 OTS方案驗(yàn)證簽名的時(shí)間

由結(jié)果可見，WOTS+方案運(yùn)行效率很低.與WOTS+相比，SOTS在生成密鑰、構(gòu)造簽名和驗(yàn)證簽名的時(shí)間上，分別減少了71.4%,47.7%和60.9%.與WOTS方案相比，SOTS以增加很短的運(yùn)行時(shí)間為代價(jià)，大量減少了空間上的占用.SOTS與NOTS,SDS-OTS方案的運(yùn)行效率相差甚小.相比于WOTS-S,SOTS在簽名和驗(yàn)證時(shí)間上有明顯減少.

6 總結(jié)和展望

在CPA模型下，SOTS數(shù)字簽名方案是存在不可偽造地高效的WOTS變體方案.在相同128 b后量子安全級別下，與WOTS相比，SOTS在密鑰和簽名尺寸上分別減少了77%和82%.與WOTS+相比，SOTS在密鑰和簽名上分別減少了60.7%和60.5%.除此之外，SOTS運(yùn)行效率高.與WOTS+相比，在生成密鑰、構(gòu)造簽名和驗(yàn)證簽名的時(shí)間上分別減少了71.4%，47.7%和60.9%.在未來的研究中，我們將應(yīng)用SOTS于分布式賬本中，基于有向無環(huán)圖設(shè)計(jì)一個(gè)抗量子的共識機(jī)制來提高分布式賬本的安全性和性能.