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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 抗量子計(jì)算的快速簽名機(jī)制HiMQ-3P

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

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

2.1 HiMQ-3P密鑰生成

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

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

2.2 HiMQ-3P簽名生成

給定一個(gè)消息m和私鑰se。

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

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

(1)

找到一個(gè)解(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)，通過解一個(gè)包含o3個(gè)變量o3個(gè)方程的線性系統(tǒng)得到(sv+o1+o2+1,…,sv+m)。則s=(s1,…,sn)是F(x)=ξ的一個(gè)解。

2.3 HiMQ-3P簽名驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法比較

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

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

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

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

5 結(jié)論

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