基于多變量二次方程的抗量子區(qū)塊鏈快速簽名算法

梁 偉，劉小歐，羅 維，馬文平，王 凌

(1.中國電信研究院，北京 102209；2.西安電子科技大學(xué)，西安 710071；3.全鏈通有限公司，北京 100191)

0 引言

區(qū)塊鏈?zhǔn)且环N新興的具有去中心化基礎(chǔ)架構(gòu)、集體維護以及安全可信等特征的分布式計算系統(tǒng)，目前已經(jīng)引起政府部門、金融機構(gòu)、科技企業(yè)和資本市場的高度重視與廣泛關(guān)注[1]。但是區(qū)塊鏈技術(shù)仍處在發(fā)展初期，與商業(yè)潛力相生相伴的是安全隱患，暴露出來的安全事故讓人們意識到，安全性問題成為區(qū)塊鏈廣泛商用的重要摯肘。

作為區(qū)塊鏈底層的安全支撐技術(shù)之一，公鑰密碼已有較為廣泛和成熟的理論體系。其中應(yīng)用最廣泛、技術(shù)與安全性能比較成熟的有RSA、DH、ECC三種傳統(tǒng)的公鑰密碼體制。然而量子計算機的出現(xiàn)，使得傳統(tǒng)公鑰密碼安全性受到嚴峻的挑戰(zhàn)，且現(xiàn)有區(qū)塊鏈系統(tǒng)的安全性也受到了不利的影響[2]。

目前已有一些相關(guān)區(qū)塊鏈項目開始部署抗量子計算的密碼技術(shù)，主要思想是使用抗量子密碼算法替換目前采用的傳統(tǒng)密碼算法。發(fā)展抗量子計算密碼是未來保證基于公鑰密碼系統(tǒng)安全性的基石和發(fā)展動力。

本文將從目前已有的區(qū)塊鏈抗量子加密技術(shù)出發(fā)，分析其算法的設(shè)計準(zhǔn)則與優(yōu)缺點，在此基礎(chǔ)上提出基于多變量二次方程的抗量子簽名機制算法，為新的區(qū)塊鏈抗量子密碼算法設(shè)計提供參考。

1 抗量子密碼研究現(xiàn)狀

為了應(yīng)對量子計算機的攻擊，在密碼學(xué)界研究者們提出了相應(yīng)的抗量子加密技術(shù)，主要包括四類：

(1)基于格理論的抗量子密碼

格密碼是基于格理論建立的密碼學(xué)技術(shù)。格是指N維線性空間的離散加法子群。格密碼的安全性是建立在格問題的最壞情況復(fù)雜性上的，格理論中有許多難解問題，迄今也還沒有發(fā)現(xiàn)有效的量子求解算法，能夠抵抗量子計算機的攻擊。

(2)基于編碼理論的抗量子密碼

編碼理論的抗量子密碼基于二元不可約的Goppa碼，是將待加密的明文看做一個合法碼字，加密過程等價于給明文碼字添加一個隨機選擇的錯誤向量，而解密過程則相當(dāng)于譯碼。只有熟悉碼的結(jié)構(gòu)并掌握有效譯碼算法才能譯碼。

(3)基于哈希函數(shù)的抗量子密碼

哈希函數(shù)相當(dāng)于把原空間的一個數(shù)據(jù)集映射到另外一個空間，其安全依賴于底層的哈希函數(shù)的抗碰撞性,完美無碰撞需要映射到的空間不小于原空間，為此，要么增大映射空間/原空間的大小，要么盡可能把原數(shù)據(jù)集均勻映射到較小空間，或者結(jié)合數(shù)據(jù)特征讓出現(xiàn)概率較大的數(shù)據(jù)集有較小的碰撞概率，出現(xiàn)概率較小的數(shù)據(jù)集有較大的碰撞概率?；诠：瘮?shù)的抗量子密碼一般用于量子簽名方案。

(4)基于多變量二次方程的抗量子密碼

多變量二次方程的抗量子密碼系統(tǒng)的安全性是基于求解一組多變量多項式為NP-C問題，而非RSA和ECC所基于的數(shù)論問題，可替代RSA和ECC以抵抗基于量子計算機攻擊的公鑰密碼體系[3]。它不僅能夠抵御二階線性化方程攻擊，而且能抵御線性化攻擊、秩攻擊、XL算法以及Grover攻擊。

目前已經(jīng)有一些區(qū)塊鏈項目開始部署抗量子計算的密碼技術(shù)，如小蟻Neo、IOTA、騰訊PQSS、Hcash(超級現(xiàn)金)等，主要思想就是使用后量子密碼算法替換目前區(qū)塊鏈系統(tǒng)采用的傳統(tǒng)密碼算法。

(1)NEO引入基于Lattice(格密碼學(xué))的簽名和加密技術(shù)，將加解密問題歸約到量子計算機尚無法解決的SVP(最短向量問題)，理論上可以預(yù)防量子危機。但目前NEO沒有公開的文檔說明其采用的抗量子密碼算法。

(2)IOTA使用的簽名算法是Winternitz One-Time Signature (W-OTS)，這是一種后量子簽名算法，可以抵御量子攻擊。W-OTS算法是One-Time的，即簽過一次名后就不能重復(fù)使用，否則會有丟錢的風(fēng)險?？梢砸粋€地址多次打錢，但取一次錢(取錢需要簽名)后就不能用了，需要換新地址。W-OTS的一個缺點是簽名長度特別大，這也是抗量子簽名普遍的缺點。

(3)Hcash使用了基于Hash函數(shù)的抗量子簽名方案(MSS/LMS)和基于格的抗量子簽名方案(Bliss)。這兩種算法帶來的缺點有：①公鑰、簽名長度遠大于傳統(tǒng)數(shù)字簽名算法ECDSA的公鑰、簽名長度，在密碼貨幣或區(qū)塊鏈系統(tǒng)中實現(xiàn)這些簽名算法將帶來交易大小顯著增加，從而引發(fā)系統(tǒng)吞吐量明顯下降;②Bliss算法中的離散高斯采樣(DGS)模塊在實現(xiàn)中存在旁路攻擊的風(fēng)險。針對這兩個問題，Hcash技術(shù)團隊已經(jīng)給出了應(yīng)對措施。但是對于第二個缺點，Hcash技術(shù)團隊沒有對應(yīng)對措施進行詳細說明，更多地是指出針對Bliss的旁路攻擊實際實現(xiàn)具有難度，攻擊不能夠成功實施。

(4)騰訊已經(jīng)有了抗量子簽名服務(wù)嘗試，如騰訊云PQSS產(chǎn)品使用騰訊云量子密鑰管理服務(wù)(QMS)生成密鑰，密鑰隨機源的隨機性來源于量子物理過。

在對現(xiàn)有抗量子計算的簽名算法進行研究和分析的基礎(chǔ)上，本文提出一種安全高效的基于多變量二次方程的簽名算法HiMQ-3P，使其廣泛地應(yīng)用于抵抗量子計算機攻擊的各個安全領(lǐng)域。

2 抗量子計算的快速簽名機制HiMQ-3P

本節(jié)將首先引出一種快速簽名算法HiMQ-3P，該算法是NIST的抗量子密碼算法候選標(biāo)準(zhǔn)，相對于其他抗量子算法，結(jié)合多變量二次方程的HiMQ-3P快速簽名算法，其簽名長度和私鑰長度具有很大優(yōu)勢，算法開銷小、簽名和驗證速度較快。

首先，對HiMQ-3P簽名算法的設(shè)計思想與算法原理進行闡述。

2.1 HiMQ-3P密鑰生成

輸入一個安全參數(shù)λ，生成一個公私鑰對〈PK,SK〉=〈P,se〉。

(2)計算公鑰P=S°F°T。

2.2 HiMQ-3P簽名生成

給定一個消息m和私鑰se。

(3)為了計算F-1(ξ)=s，尋找s滿足F(s)=ξ。

隨機選一個向量sv=(s1,…,sv)，將sv插入F(i),(i=1,…,o1)得到一個包含o1個變量o1個方程的二次方程組，計算下列矩陣相乘：

(1)

找到一個解(sv+1,…,sv+o1)；將(sv+1,…,sv+o1)插入F(i),(i=o1+1,…,o1+o2)，類似地得到(sv+o1+1,…,sv+o1+o2)；將(s1,…,sv+o1+o2)插入F(i),(i=o1+o2+1,…,m)，通過解一個包含o3個變量o3個方程的線性系統(tǒng)得到(sv+o1+o2+1,…,sv+m)。則s=(s1,…,sn)是F(x)=ξ的一個解。

2.3 HiMQ-3P簽名驗證

給定簽名τ、消息m和公鑰P，驗證P(τ)=h(m)是否相等。如果相等，則簽名有效。否則，簽名無效。

HiMQ-3P簽名算法具有諸多優(yōu)勢，其中最為突出的優(yōu)點有：

(1)簽名長度小。區(qū)塊的大小相應(yīng)地也比現(xiàn)有抗量子計算的區(qū)塊鏈的區(qū)塊小很多。

(2)簽名和驗證速度快。比同等安全等級的RSA和ECDSA算法速度還快，這樣使得發(fā)起交易和驗證交易的速度有一定的提升，有潛力滿足金融系統(tǒng)高頻次的交易需求。

(3)節(jié)點的私鑰尺寸小。在私鑰保密方面，該方法中對私鑰的安全維護將會比其他系統(tǒng)更容易。

3 基于多變量二次方程的區(qū)塊鏈快速簽名算法

結(jié)合HiMQ-3P簽名算法原理，本文提出一種基于多變量二次方程的區(qū)塊鏈快速簽名算法。該簽名算法安全性依賴于有限域上的多變量二次多項式映射，能夠有效地抵抗密鑰恢復(fù)攻擊、基于秩的攻擊和量子計算攻擊，安全性非常高。下面詳細介紹該算法的實現(xiàn)過程。

基于多變量二次方程的區(qū)塊鏈快速簽名算法流程圖如圖1所示。

圖1 基于多變量二次方程的抗量子區(qū)塊鏈簽名算法流程圖

該算法的具體實現(xiàn)過程如下：

(1)新節(jié)點i進入系統(tǒng)后，得到自己公私鑰對(pki,ski)(這里采用基于多元二次方程的高效簽名算法HiMQ-3P)，將私鑰ski保密存儲在一個文件或數(shù)據(jù)庫中，通過客戶端(錢包)進行管理。節(jié)點i通過安裝客戶端得到其他節(jié)點的公鑰列表，并同步整個區(qū)塊鏈。同時，節(jié)點i向網(wǎng)絡(luò)(P2P網(wǎng)絡(luò))中其他節(jié)點廣播自己的公鑰pki，其他節(jié)點收到節(jié)點i的公鑰后加入到自己的公鑰列表中用來對后續(xù)的節(jié)點i發(fā)起的交易進行驗證。

(2)節(jié)點A向節(jié)點B發(fā)起一筆交易M={A支付3個Unicorn幣給B}，這里只是簡單的交易信息文本，具體的交易結(jié)構(gòu)還包括其他相關(guān)信息如時間戳等。節(jié)點A先使用SHA-3哈希算法對交易M進行壓縮SHA-3(M)，使用自己的私鑰skA計算M的簽名SigskA(SHA-3(M))。節(jié)點A將交易消息M與簽名SigskA(SHA-3(M))并置M‖SigskA(SHA-3(M))廣播到網(wǎng)絡(luò)中。其他節(jié)點收到節(jié)點A發(fā)的交易消息后，從本地的節(jié)點公鑰列表中查找節(jié)點的公鑰pkA，使用其對應(yīng)交易簽名值進行驗證，并確認該交易是否有效。

(3)為了生成一個區(qū)塊，通過共識機制，記賬節(jié)點將時間間隔內(nèi)的所有交易記錄M‖SigskA(M)打包進新的區(qū)塊。網(wǎng)絡(luò)中的每個節(jié)點獨立對新的區(qū)塊進行驗證并鏈接到區(qū)塊鏈中，所有誠實節(jié)點共同維護唯一可驗證的主鏈。

4 算法比較

在本節(jié)中將本文中提出的基于多變量二次方程的抗量子密碼與其他算法進行對比分析。

表1給出了HiMQ-3P簽名算法與其他簽名算法在簽名長度、公私鑰長度、簽名/驗證效率方面的比較(比較單位為簽名cycle數(shù))。從表1中可以看出，在實現(xiàn)128 bit的安全性前提下，ECDSA-256具有最小的簽名長度和公鑰長度；BLISS和DILITHIUM是由Léo Ducas等人提出的兩種基于格的簽名算法，BLISS簽名算法不能夠抵抗邊信道攻擊，因此作者提出了更安全的DILITHIUM簽名算法，在保證相同安全性的前提下DILITHIUM簽名算法具有較小的簽名長度和公私鑰長度，并且已提交NIST的后量子密碼算法候選標(biāo)準(zhǔn)。

基于多變量二次方程的快速簽名算法HiMQ-3P也是NIST的后量子密碼算法候選標(biāo)準(zhǔn)，其簽名長度和私鑰長度較BLISS和DILITHIUM簽名算法具有一定的優(yōu)勢。HiMQ-3P算法簽名和驗證速度分別是ECDSA的3.6倍和21.17倍；HiMQ-3P算法簽名和驗證速度分別是BLISS的7.86倍和6.96倍。此外，HiMQ-3P簽名算法的安全性依賴于有限域上的多變量二次多項式映射，能夠有效地抵抗密鑰恢復(fù)攻擊、基于秩的攻擊和量子計算攻擊。

表1 不同簽名算法性能比較

5 結(jié)論

本文提出了一種基于多變量二次方程的抗量子密碼算法。首先給出其核心設(shè)計思想HiMQ-3P簽名驗證，并在此基礎(chǔ)上結(jié)合多變量二次方程提出新的抗量子計算密碼。最后通過比較本文中提出的算法與現(xiàn)有其他算法，得出該算法在簽名長度、公私鑰長度、簽名以及驗證效率等方面的性能都有顯著提升，且可以有效抵抗量子計算機的攻擊，為推動區(qū)塊鏈安全性能的提升提供了新的設(shè)計思路。