劉 昂 文 津 許盛偉 陳 穎 秦曉宏 藍(lán)浩書

1(北京電子科技學(xué)院網(wǎng)絡(luò)信息化管理處 北京 100070)

2(北京郵電大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 北京 100876)

3(北京電子科技學(xué)院網(wǎng)絡(luò)空間安全系 北京 100070)

4(北京電子科技學(xué)院信息安全研究所 北京 100070)

5(北京電子科技學(xué)院密碼科學(xué)與技術(shù)系 北京 100070)

2008年,Nakamoto[1](中本聰)首次引出了區(qū)塊鏈的概念.此后,區(qū)塊鏈技術(shù)得到全世界學(xué)者的深入研究,并在各行各業(yè)得到廣泛應(yīng)用.

我國非常重視區(qū)塊鏈的發(fā)展,2016年,國務(wù)院首次將區(qū)塊鏈技術(shù)作為戰(zhàn)略性前沿技術(shù)列入《“十三五”國家信息化規(guī)劃》[2];2019年10月24日,十九屆中共中央政治局就區(qū)塊鏈技術(shù)發(fā)展現(xiàn)狀和趨勢進(jìn)行第十八次集體學(xué)習(xí),強(qiáng)調(diào)“把區(qū)塊鏈作為核心技術(shù)自主創(chuàng)新重要突破口,加快推動(dòng)區(qū)塊鏈技術(shù)和產(chǎn)業(yè)創(chuàng)新發(fā)展”[3],區(qū)塊鏈已被提升到國家戰(zhàn)略高度;2021年兩會后,區(qū)塊鏈作為數(shù)字經(jīng)濟(jì)7個(gè)重點(diǎn)領(lǐng)域被寫入十四五規(guī)劃綱要[4],表明2021—2025年區(qū)塊鏈已被列入政府重點(diǎn)工作內(nèi)容.

區(qū)塊鏈?zhǔn)且环N鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)[5],以區(qū)塊(block)的形式存儲數(shù)據(jù),區(qū)塊按照生成時(shí)間順序組成1條鏈,1個(gè)區(qū)塊中存在多筆交易信息,多個(gè)區(qū)塊通過哈希值前后連接,形成一個(gè)“區(qū)塊鏈”.

區(qū)塊鏈從本質(zhì)上講是一個(gè)共享信息數(shù)據(jù)庫[6],存儲于其中的數(shù)據(jù)或信息具有“不可偽造”“不可篡改”“全程留痕”“可以追溯”“公開透明”“集體維護(hù)”等特征.基于這些特征,區(qū)塊鏈技術(shù)奠定了堅(jiān)實(shí)的“信任”基礎(chǔ),創(chuàng)造了可靠的“合作”機(jī)制,具有廣闊的應(yīng)用前景.

區(qū)塊鏈在網(wǎng)絡(luò)安全中扮演著至關(guān)重要的角色[7],可以降低可能導(dǎo)致整個(gè)網(wǎng)絡(luò)故障的網(wǎng)絡(luò)攻擊風(fēng)險(xiǎn).然而量子計(jì)算機(jī)以其強(qiáng)大的并行計(jì)算能力,可以輕松破解經(jīng)典計(jì)算機(jī)難以破解的數(shù)學(xué)困難問題[8],從而對現(xiàn)代密碼技術(shù)尤其是公鑰密碼構(gòu)成安全威脅.量子計(jì)算對傳統(tǒng)密碼學(xué)的影響極大程度地威脅了區(qū)塊鏈系統(tǒng)的安全穩(wěn)定發(fā)展.Grover量子算法在搜索上較經(jīng)典搜索算法能提供2次加速,從而能加速對哈希函數(shù)的前像碰撞攻擊[9].量子計(jì)算機(jī)的大規(guī)模應(yīng)用將對哈希函數(shù)的安全性造成巨大影響[10],進(jìn)而給網(wǎng)絡(luò)安全帶來巨大隱患[11-12],所以研究具有抗量子性的哈希函數(shù)意義重大.

本文將首先研究量子計(jì)算機(jī)對區(qū)塊鏈中的哈希函數(shù)的攻擊形式,然后開展區(qū)塊鏈中哈希函數(shù)的抗量子安全性研究,對當(dāng)前區(qū)塊鏈中的哈希函數(shù)的設(shè)計(jì)進(jìn)行歸納和總結(jié),最后對后量子時(shí)代區(qū)塊鏈中的哈希函數(shù)的設(shè)計(jì)提出有益建議并對前景進(jìn)行了展望.

1 哈希函數(shù)及其面臨的量子計(jì)算攻擊威脅

1.1 哈希函數(shù)定義及其性質(zhì)

作為區(qū)塊鏈的起源性技術(shù),哈希函數(shù)在區(qū)塊鏈的數(shù)據(jù)完整性保護(hù)上發(fā)揮著不可替代的作用,哈希函數(shù)的抗第二原像性(弱抗碰撞性)直接決定了區(qū)塊鏈的不可篡改性[13].

哈希函數(shù)又稱散列函數(shù),是密碼學(xué)上一類將任意長度的消息映射到某一固定長度的哈希值的單向函數(shù),它滿足以下3個(gè)基本性質(zhì)[14]:

1) 抗原像性.對任意給定的哈希值h,尋找1個(gè)消息x,使得H(x)=h在計(jì)算上不可行.

2) 弱抗碰撞性.給定消息x,其哈希值h=H(x),尋找1個(gè)不同于消息x的消息x′,滿足h=H(x′)在計(jì)算上不可行.

3) 強(qiáng)抗碰撞性.尋找2個(gè)不同的消息x和x′,使得H(x)=H(x′)在計(jì)算上不可行.

1953年,IBM公司提出,為提高對數(shù)據(jù)庫文件的檢索效率,為每個(gè)文件生成1個(gè)電子指紋,搜索文件時(shí)直接搜索其電子指紋就能將文件搜索出來,簡單高效.1981年,為提升數(shù)字簽名RSA的安全性,避免偽造攻擊,防止數(shù)據(jù)被篡改,Davis和Price提出密碼哈希函數(shù)的概念[15].數(shù)據(jù)被篡改后電子指紋發(fā)生變化,從而發(fā)現(xiàn)篡改行為,進(jìn)而保證數(shù)字簽名的安全性.對文件進(jìn)行數(shù)字簽名時(shí),僅對其摘要值而非原文件進(jìn)行簽名即可,提升數(shù)字簽名效率.摘要值長度從128b,160b,192b,256b,384b,…,512b不等,高效便捷.當(dāng)前主流的基于公鑰的數(shù)字簽名,即運(yùn)用哈希函數(shù)對文件生成定長的摘要值后進(jìn)行數(shù)字簽名.

1.2 針對哈希函數(shù)的量子計(jì)算攻擊

哈希函數(shù)在區(qū)塊鏈系統(tǒng)中應(yīng)用廣泛,以比特幣平臺為例,在交易中使用哈希函數(shù)對每一筆交易生成摘要值后作數(shù)字簽名;在鏈上數(shù)據(jù)的完整性保護(hù)上,使用哈希函數(shù)及基于哈希函數(shù)的Merkle樹結(jié)構(gòu)作完整性校驗(yàn),并使用哈希值完成前后區(qū)塊的連接;在工作量證明(proof of work, PoW)共識機(jī)制中使用尋找哈希函數(shù)特定輸出對應(yīng)的輸入作為數(shù)學(xué)難題來為礦工分配新區(qū)塊的記賬權(quán).

以Grover算法為代表的量子算法能有效實(shí)施針對經(jīng)典哈希函數(shù)的量子計(jì)算攻擊,攻擊形式主要是原像攻擊和第二原像攻擊.

1.2.1 挖礦攻擊

原像攻擊:在密碼學(xué)中,哈希函數(shù)上的原像攻擊用于尋找有著特定哈希值的消息,1個(gè)哈希函數(shù)應(yīng)該抵御對其原像的攻擊.即給定y,找到1個(gè)原像x,使得H(x)=y.在比特幣中,礦工們通過尋找滿足哈希值為特定值的NONCE來獲得新區(qū)塊記賬權(quán)和挖礦獎(jiǎng)勵(lì)(新比特幣的產(chǎn)生).比特幣挖礦就是發(fā)現(xiàn)新區(qū)塊、驗(yàn)證待確認(rèn)交易并將其添加到比特幣區(qū)塊鏈的過程.量子攻擊者使用Grover算法加速搜索,能很快找到原像,從而在挖礦游戲中取得壓倒性優(yōu)勢,甚至壟斷記賬權(quán),從而大大破壞比特幣系統(tǒng)的去中心化程度,這就是針對PoW共識機(jī)制的挖礦攻擊.該攻擊將導(dǎo)致51%攻擊,即擁有量子計(jì)算機(jī)的礦工能憑借壓倒性的算力優(yōu)勢將壟斷新區(qū)塊的生成,破壞區(qū)塊鏈的去中心化[16].

為提高對原像攻擊的抗性,雙重哈希是一種可以抵御在某種情況下攻擊者已經(jīng)破解了首個(gè)哈希的好策略.比特幣系統(tǒng)使用雙重哈希SHA-256,這是一種2000年代減緩哈希破解的常見手段[17].然而量子攻擊者使用的是暴力破解手段,雙重哈希結(jié)構(gòu)并未改變像(輸出)的空間大小,因而不能有效抵抗量子敵手的原像攻擊.

1.2.2 偽造攻擊

第二原像攻擊:攻擊者在哈希值維持不變的前提條件下找到假消息m′替換合法消息m,即尋找m′使得H(m′)=H(m).在比特幣為代表的區(qū)塊鏈系統(tǒng)中,攻擊者通過尋找哈希沖突,對區(qū)塊鏈上的數(shù)據(jù)實(shí)施第二原像攻擊,使用非法數(shù)據(jù)篡改合法交易數(shù)據(jù),并且由于哈希值維持不變,也不會被校驗(yàn)發(fā)現(xiàn).這就是針對鏈上數(shù)據(jù)的偽造(篡改)攻擊.

哈希函數(shù)是把任意長度的輸入(又叫作預(yù)映射(pre-image))通過哈希算法變換成固定長度的哈希值輸出,因此這種轉(zhuǎn)換是一種壓縮映射,即哈希值的空間通常遠(yuǎn)小于輸入的空間,不同的輸入可能會哈希成相同的輸出,因而從映射角度看,哈希函數(shù)顯然是多對1映射,因此理論上必然存在碰撞,這也正是量子敵手成功實(shí)施第二原像攻擊的基礎(chǔ),但是并非所有的消息都有第二原像.

近年來,大量研究量子計(jì)算機(jī)的機(jī)構(gòu)和學(xué)者利用量子力學(xué)現(xiàn)象解決常規(guī)計(jì)算機(jī)難以解決的數(shù)學(xué)困難性問題.2019年,Google團(tuán)隊(duì)就在1臺53b的量子計(jì)算機(jī)上僅用200s便完成了在超級計(jì)算機(jī)上需要1萬年的計(jì)算[18],顯示了量子計(jì)算超強(qiáng)的運(yùn)算速度與處理能力,也透露出量子技術(shù)對區(qū)塊鏈的潛在威脅.有研究顯示,Bitcoin,Ethereum,Dash,Litecoin,Zcash,Monero,Ripple,NXT,Byteball,Bytecoin,IOTA等區(qū)塊鏈均已受到量子威脅影響[19].而哈希函數(shù)在區(qū)塊鏈中扮演重要角色,被王小云院士視為區(qū)塊鏈的起源性技術(shù).哈希函數(shù)在區(qū)塊鏈中具有加密數(shù)據(jù)、驗(yàn)證數(shù)據(jù)、身份認(rèn)證等重要功能,區(qū)塊鏈數(shù)據(jù)的不可篡改等特性就是哈希函數(shù)的抗碰撞性確保的.如果大型量子計(jì)算機(jī)被完全研發(fā)出來,它們將對當(dāng)前的經(jīng)典密碼算法尤其公鑰密碼造成毀滅性的災(zāi)難,許多協(xié)議、算法將不再是安全的[20].

量子敵手可以使用Grover算法通過搜索哈希沖突,在不改變哈希值的條件下篡改某一筆交易而不被發(fā)現(xiàn).Grover的搜索算法[22]允許在計(jì)算逆哈希函數(shù)時(shí)實(shí)現(xiàn)2次加速效果,這種攻擊將允許攻擊者篡改鏈上的合法交易,破壞區(qū)塊鏈上的數(shù)據(jù)完整性.例如,文獻(xiàn)[23]使用Grover算法查找哈希函數(shù)中的沖突,得出哈希函數(shù)必須輸出3n位才能提供n位安全級別的結(jié)論.這樣的結(jié)論意味著許多當(dāng)前的哈希函數(shù)在后量子時(shí)代將無效,而其他像SHA-2或SHA-3這樣的函數(shù)將不得不增加其輸出大小.

以使用Merkle樹的比特幣為例,量子敵手可以通過使用Grover算法構(gòu)造數(shù)據(jù),使得構(gòu)造出的數(shù)據(jù)與真實(shí)數(shù)據(jù)通過同一個(gè)哈希函數(shù)計(jì)算出的值相同,以達(dá)到篡改數(shù)據(jù)并維持哈希值不變從而不被發(fā)現(xiàn)的目的.例如在圖1的Merkle樹中,敵手構(gòu)造的數(shù)據(jù)Tx′與原始數(shù)據(jù)Tx通過同一哈希函數(shù)計(jì)算出的哈希值相同,即H(Tx)=H(Tx′),從而用Tx′替換原始數(shù)據(jù)Tx,其哈希值及Merkle根將維持不變,以實(shí)現(xiàn)前像碰撞攻擊.

圖1 前像碰撞攻擊

2 哈希函數(shù)對比分析

本文對5種哈希算法進(jìn)行了對比分析,其輸入、輸出、優(yōu)點(diǎn)與缺點(diǎn)如表1所示:

表1 哈希算法總結(jié)

2.1 傳統(tǒng)經(jīng)典哈希算法

自1953年Hans Peter Luhn提出哈希函數(shù)[24]以來,1970年哈希函數(shù)蓬勃發(fā)展,2001年美國國家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology, NIST)發(fā)布SHA-256算法[25],2008年中本聰[1]將哈希函數(shù)應(yīng)用到區(qū)塊鏈中,并成為區(qū)塊鏈技術(shù)不可撼動(dòng)的基石.

SHA-256算法屬于SHA-2系列,在2008年被公認(rèn)為最安全最先進(jìn)的算法之一,中本聰提出的比特幣除了生成地址中有一個(gè)環(huán)節(jié)使用了REPID-160算法,其他需要作哈希運(yùn)算的地方均使用SHA-256,SHA-256是最早運(yùn)用于區(qū)塊鏈中的哈希函數(shù)之一.其他的傳統(tǒng)經(jīng)典哈希算法Ethash,Scrypt,RIPEMD160等,下面具體介紹SHA-256.

SHA-256[26]是一個(gè)Merkle-Damgard結(jié)構(gòu)的迭代哈希函數(shù),如圖2所示,計(jì)算流程是一個(gè)迭代計(jì)算的過程,當(dāng)最后一個(gè)消息塊處理完畢以后,最終的輸出值就是所輸入的原始消息的SHA-256值.

圖2 SHA-256算法流程

SHA-256通過將不定長的消息和文件等數(shù)據(jù)轉(zhuǎn)換為固定長度為256b且難以區(qū)分的字符串來保護(hù)數(shù)據(jù)不被截取或篡改.相同的輸入依據(jù)SHA-256計(jì)算的值是唯一的,但當(dāng)輸入有修改時(shí),即使是很微小的修改得到的哈希結(jié)果也會完全不同.SHA-256算法的特點(diǎn)是易于檢查,較難偽造,具有很強(qiáng)的抗強(qiáng)碰撞的能力.以現(xiàn)在的計(jì)算機(jī)破解需要消耗極大的資源,因此無法獲得利益.但隨著量子計(jì)算機(jī)的發(fā)展,SHA-256的安全性也將受到影響.據(jù)文獻(xiàn)[19]顯示,SHA-256的前量子安全級別為256b,預(yù)估后量子安全級別為128b.

其他傳統(tǒng)經(jīng)典哈希算法同樣受到量子計(jì)算機(jī)不同程度的影響,具體如表2所示:

表2 傳統(tǒng)經(jīng)典哈希算法受量子計(jì)算機(jī)的影響情況

2.2 基于量子密鑰的Toeplitz哈希算法

2018年,Kiktenko等人[27]使用Toeplitz哈希計(jì)算認(rèn)證標(biāo)簽值,Toeplitz哈希計(jì)算簡單,且在信息理論上是安全的.

Toeplitz哈希是一類特殊的通用哈希函數(shù)[28],基于Toeplitz矩陣進(jìn)行哈希值的計(jì)算[29].維數(shù)為n×m的Toeplitz矩陣通過向量矩陣乘法可以將長度為m的原始消息計(jì)算為長度為n的哈希結(jié)果.Toeplitz矩陣是在左右對角線上具有常數(shù)值的矩陣.這種特定結(jié)構(gòu)減少了構(gòu)造隨機(jī)矩陣時(shí)所需的隨機(jī)比特?cái)?shù).例如,當(dāng)構(gòu)造m×n對角常數(shù)矩陣時(shí),所需的隨機(jī)比特?cái)?shù)將從mn減少到m+n-1.

文獻(xiàn)[27]采用的方案中,如果通信雙方Alice和Bob共享一個(gè)其他人不知道的秘密私鑰Kaut,則可以對接收到的對方消息進(jìn)行身份驗(yàn)證.秘密私鑰生成的前提是雙方在會話開始時(shí)就有少量“種子”密鑰來認(rèn)證對方的身份.一旦建立了私鑰,身份驗(yàn)證過程則是:Alice向Bob發(fā)送1條消息,其中包含使用該密鑰生成的哈希標(biāo)簽.在收到消息后,Bob計(jì)算其哈希標(biāo)記.如果哈希標(biāo)記一致,Bob可以確定該消息是從Alice發(fā)送的.哈希標(biāo)簽的具體計(jì)算公式如下:

h(Mi)=TSMi⊕ri,

(1)

其中TS是由長度為lh+lM-1的字符串S生成的lh×lMToeplitz矩陣,ri是長度為lh的位串,⊕是按位異或,S和ri都是私有的,并且取自公共私鑰Kaut.那么竊聽者正確猜測已被修改消息的哈希標(biāo)簽的概率不超過2-lh.如果傳輸了一系列消息,則可以在不影響安全性的情況下再次使用字符串S,而每次都必須重新生成字符串ri.私鑰以每條消息lh(單位為b)的速率被消耗.其中l(wèi)h=40,lM=222.

如果一個(gè)裝有量子計(jì)算機(jī)的惡意方離線偽造數(shù)據(jù)庫.它將過去的一個(gè)交易記錄更改為自己的利益,并對同一塊中的其他交易的變體進(jìn)行Grover搜索,以使其哈希保持不變,從而使偽造版本看起來合法.一旦搜索成功,它就會入侵所有或部分網(wǎng)絡(luò)節(jié)點(diǎn),并用偽造的版本替換合法數(shù)據(jù)庫.然而,這種攻擊造成重大損害的可能性似乎很低,因?yàn)楣粽咝枰瑫r(shí)攻擊至少1/3的節(jié)點(diǎn)才能改變共識.此外,由于與經(jīng)典搜索算法相比,Grover算法只提供了2次加速,因此可以通過將塊哈希長度的約定增加到其安全非量子值的2倍來防止這種情況.

該哈希函數(shù)采用一次一密的加密方式,在信息理論上絕對安全[27],可以有效抵御量子攻擊,為實(shí)現(xiàn)可擴(kuò)展的量子安全區(qū)塊鏈平臺開辟了可能性.私鑰生成前的“種子”密鑰認(rèn)證了通信雙方的身份,為算法提供了更高的安全性,但是成本太高,無法大規(guī)模應(yīng)用于實(shí)踐.通信只在兩方之間進(jìn)行,第三方無法驗(yàn)證,存在通信一方作惡的可能性,竊聽者也可以冒充2個(gè)授權(quán)用戶(Alice和Bob)中的任何一個(gè),以獲得對機(jī)密數(shù)據(jù)和資源的未經(jīng)授權(quán)的訪問.

2.3 基于QIQW的量子哈希算法

2021年,Abd El-Latif等人[7]提出了使用基于QIQW(quantum-inspired quantum walks)的量子哈希函數(shù)鏈接區(qū)塊鏈的塊.量子漫步可以描述為希爾伯特空間元素到概率分布集合的非線性映射.這種性質(zhì)加上量子漫步對初始條件變化的高度敏感性,使離散量子漫步可以被視為離散時(shí)間和離散值混沌系統(tǒng).離散量子漫步的基本組成部分是硬幣粒子、漫步空間、進(jìn)化算子和1組可觀察量.在這種情況下,如果量子漫步在有N個(gè)頂點(diǎn)的圓上運(yùn)行,步行者是一個(gè)運(yùn)行在基數(shù)為#(H)=N的希爾伯特空間H中的量子系統(tǒng).受控交替量子漫步(controlled alternating quantum walks, CAQW)是由二進(jìn)制串m控制的2維單步量子漫步.文獻(xiàn)[7]中正是基于CAQW的混沌行為構(gòu)建了量子哈希函數(shù).

基于CAQW構(gòu)建量子哈希函數(shù)(quantum hash functions, QHF)的步驟為:

2) 通過使用等式h=fix(Pi×108) mod 2g將概率矩陣P轉(zhuǎn)換為比特串,獲得二進(jìn)制消息m的哈希值,其中哈希值的長度為N2×g(單位為b).

假設(shè)使用標(biāo)準(zhǔn)量子通信信道在發(fā)送方和接收方之間交換主密鑰參數(shù)(N,α,β,θ0,θ1,θ2).交換的密鑰參數(shù)在消息加密、解密和身份驗(yàn)證過程都是需要的.

Alice和Bob通過防篡改的量子安全信道交換初始參數(shù)(N,α,β,θ0,θ1,θ2).數(shù)字設(shè)備的計(jì)算精度為10-16,用于構(gòu)造哈希值和密鑰流的密鑰空間允許為1096,這提供了額外的通信安全層.因此,基于QIQW的量子哈希函數(shù)可以防止消息攻擊.

假設(shè)Bob收到交易信息后,Bob根據(jù)與Alice交換的初始密鑰參數(shù)(N,α,β,θ0,θ1,θ2)從S提取哈希碼hashA,從接收到的加密文本中提取哈希碼hashB.接下來,將hashA與hashB一起比對.若發(fā)現(xiàn)加密文本并非Alice所發(fā),該筆交易被丟棄.因此,基于QIQW的量子哈希函數(shù)可以防止無消息攻擊.

當(dāng)Eve冒充Alice并試圖與Bob通信時(shí),Eve無法訪問初始參數(shù)(N,α,β,θ0,θ1,θ2)以操作QHF并向Bob發(fā)送未經(jīng)授權(quán)的事務(wù).Bob將通過身份驗(yàn)證過程檢測到Eve的存在并丟棄此事務(wù).同時(shí),如果Eve冒充Bob并試圖與Alice通信,Eve無法訪問有關(guān)關(guān)鍵參數(shù)(調(diào)用QHF所需的參數(shù))的信息違反交易數(shù)據(jù)的可能性.如前所述,QHF的巨大密鑰空間使得違反事務(wù)數(shù)據(jù)變得不切實(shí)際.此外,如果Eve成功獲得密碼文本及其嵌入的哈希值(即Eve成功猜測了N),Eve無法獲得受量子信道保護(hù)的完整密鑰參數(shù),就無法訪問交易數(shù)據(jù).因此,基于QIQW的量子哈希函數(shù)可以防止模擬攻擊.

基于QIQW的量子哈希函數(shù)可以抵御來自數(shù)字和量子計(jì)算機(jī)的可能攻擊[7],從而確保后量子時(shí)代物聯(lián)網(wǎng)設(shè)備之間的數(shù)據(jù)安全傳輸.為基于量子啟發(fā)模型設(shè)計(jì)區(qū)塊鏈技術(shù)打開大門,是本文目前較為推薦的哈希方案.

2.4 基于Hilbert變換的量子哈希算法

2021年,Wen等人[30]提出了一種基于Hilbert變換的量子哈希算法,并與量子SWAP測試和量子隱形傳態(tài)一起構(gòu)造了一種具有后量子安全性的量子區(qū)塊鏈系統(tǒng).其中的量子哈希算法具體構(gòu)造如下:

給定一個(gè)經(jīng)典量子函數(shù)ψ,它將1個(gè)n位0/1字符串映射到1個(gè)具有n個(gè)量子位的量子態(tài).

ψ:{0,1}n→(H2)?s,

(2)

其中

(H2)?s=H2?…?H2=H2s

(3)

是由s個(gè)量子位的單個(gè)量子位狀態(tài)空間組成的2s維Hilbert空間中的單位向量.函數(shù)ψ也可以用狄拉克符號表示為ψ:ω→|ψ(ω)〉.

如果ψ滿足以下2點(diǎn)則為量子單向函數(shù):

1) 容易進(jìn)行正向計(jì)算.即存在1個(gè)量子算法可以滿足在多項(xiàng)式時(shí)間內(nèi)計(jì)算任何輸入ω的輸出|ψ(ω)〉.

2) 根據(jù)給定的|ψ(ω)〉值無法計(jì)算出ω.即根據(jù)量子信息理論,無法從|ψ(ω)〉得到ω.

|ψ(ω)〉的性質(zhì):如果n?s,那么就不可能從給定的|ψ(ω)〉中獲得ω的值.

對于任意1對輸入ω和ω′,ω≠ω′,如果函數(shù)ψ的映射是ω→|ψ(ω)〉,則|ψ(ω)〉和|ψ(ω′)〉是δ-正交,即|〈ψ(ω)〉|ψ(ω′)〉|<δ,該函數(shù)稱為δ-resistance函數(shù).

如果函數(shù)ψ:{0,1}n→(H2)?s同時(shí)是一個(gè)量子單向函數(shù)和δ-resistance函數(shù),那么這個(gè)函數(shù)被稱為(n,s,δ)量子哈希函數(shù).

根據(jù)輸入情況不同,將判定結(jié)果中測量結(jié)果、測量結(jié)果概率、判定結(jié)果、是否判定正確的統(tǒng)計(jì)如表3所示:

表3 不同輸入情況的判定結(jié)果統(tǒng)計(jì)

2.5 基于數(shù)學(xué)困難問題的哈希算法

1900年,德國數(shù)學(xué)家Hilbert[31]在巴黎第2屆國際數(shù)學(xué)家大會上作的題為《數(shù)學(xué)問題》的著名講演中,提出23個(gè)問題作為對未來數(shù)學(xué)家的挑戰(zhàn),整系數(shù)多項(xiàng)式是否存在整數(shù)解的難題正是其中的第10個(gè).1970年蘇聯(lián)數(shù)學(xué)家馬蒂塞維奇最終證明:在一般情況下,答案是否定的.

求解整數(shù)多項(xiàng)式方程組的問題就是找到一個(gè)可行的辦法,通過有限次的運(yùn)算確定含有任意多個(gè)未知數(shù)的整系數(shù)不定方程fi=(x1,x2,…,xn)=0,i=1,2,…,m的解.該問題在算法上無法解決,此外,如果多項(xiàng)式的次數(shù)≥3且n>m,那么這個(gè)問題在算法上是整數(shù)不可解的.

2018年,Krendelev等人[32]提出了一種哈希函數(shù)構(gòu)建方法,該方法基于求解整數(shù)多項(xiàng)式方程組的問題,并使用1組參數(shù)增強(qiáng)哈希函數(shù)持久性,其中方程的數(shù)量小于未知參數(shù)的數(shù)量.

該方法在構(gòu)建時(shí)需要首先確認(rèn)參數(shù),在基礎(chǔ)版本中,需要確認(rèn)的參數(shù)有:模塊p,維度大小m×n,開始系數(shù)集合α1,α2,…,αn,塊的大小b,形成被加數(shù)h1(x),h2(x),…,hm(x)的規(guī)則.為了獲得更好的結(jié)果,作者還制定了參數(shù)要求.所有計(jì)算都將在模塊p上進(jìn)行.模塊應(yīng)該是足夠大的素?cái)?shù).根據(jù)從參數(shù)α1,α2,…,αn,αi∈導(dǎo)出的特殊規(guī)則生成一些向量集,其中n是任意整數(shù),代表這些向量的維數(shù)為n.假設(shè)某個(gè)哈希文檔由1組數(shù)字描述為x=(x1,x2,…),一定數(shù)量的比特組合形成1個(gè)數(shù)字,一定數(shù)量的數(shù)字組合形成1個(gè)條件塊.塊的位數(shù)可以是8,10,12等.該哈希算法的具體計(jì)算過程如下:

1) 數(shù)據(jù)準(zhǔn)備.

根據(jù)輸入文件準(zhǔn)備1個(gè)十進(jìn)制整數(shù)字符串x=(x1,x2,…,xm).

然后根據(jù)開始系數(shù)集合α1,α2,…,αn生成一個(gè)矩陣A=(a1,a2,…,am),其中ai根據(jù)公式ai=α1a1+α2a2+…+αnan構(gòu)造為遞歸序列.

2) 構(gòu)造哈希函數(shù).

H(x)=[a1h1(x)+a2h2(x)+…+
amhm(x)] mod (p).

(4)

根據(jù)上述公式構(gòu)建的向量即是哈希,其中函數(shù)h1(x),h1(x),…,hm(x)可以自己選擇任何規(guī)則構(gòu)建,也可以按照公式計(jì)算:

H(x)=[a1x1x2+a2x2x3+…+
amxmx1] mod (p),

(5)

哈希函數(shù)的輸出字符串的大小為n×m.

3) 修改.

在大文件中,某些項(xiàng)為0的概率是很大的.其主要原因是當(dāng)某些項(xiàng)的0累加時(shí),形成一個(gè)遞歸序列的規(guī)則.為了在算法的基礎(chǔ)版本中避免這種情況,作者使用循環(huán)移位的方法.或者直接將0分量替換為固定數(shù),固定數(shù)也可以是一個(gè)參數(shù).

該哈希算法對量子計(jì)算機(jī)具有抵抗力,并基于算法上無法解決的問題——尋找整數(shù)多項(xiàng)式方程組的解實(shí)現(xiàn).所開發(fā)的算法是參數(shù)化的,因此哈希函數(shù)的結(jié)果取決于幾個(gè)參數(shù),只要參數(shù)有一點(diǎn)變化,函數(shù)的值就會發(fā)生很大變化(雪崩效應(yīng)),大大增加了決策時(shí)間.按位比較,雪崩效應(yīng)約為47%～50%,它能夠抵抗沖突.碰撞在理論上是可能的.然而,為該哈希算法找到?jīng)_突是沒有意義的,因?yàn)槿绻匠探M中存在次數(shù)大于3的多項(xiàng)式,則問題在算法上是無法解決的,因此碰撞是不可能的[32].但是同基于概率分布矩陣的量子哈希函數(shù),秘密參數(shù)的知悉范圍非常關(guān)鍵,若范圍太大則很容易遭受敵人攻擊,范圍太小則不易于第三方進(jìn)行消息驗(yàn)證,秘密參數(shù)知悉范圍的選取建議根據(jù)實(shí)際問題進(jìn)行具體判定.

3 哈希函數(shù)設(shè)計(jì)建議

區(qū)塊鏈對未來數(shù)據(jù)存儲至關(guān)重要,而區(qū)塊鏈中哈希函數(shù)的安全性更是時(shí)刻影響著區(qū)塊鏈的總體安全性,因此研究具有抗量子性的哈希函數(shù)為區(qū)塊鏈在后量子時(shí)代的穩(wěn)健運(yùn)行提供有力基礎(chǔ)具有十分重要的意義.本文在以上提出的5種哈希方案中,目前最推薦2.2節(jié)中基于QIQW的量子哈希函數(shù),可以抵御來自數(shù)字和量子計(jì)算機(jī)的可能攻擊.2.3節(jié)中的方案由于存在誤差,所以目前不推薦,未來消除誤差后,將其應(yīng)用到區(qū)塊鏈中也是一個(gè)不錯(cuò)的選擇.

除此以外,經(jīng)過分析與總結(jié),本文建議在未來區(qū)塊鏈的設(shè)計(jì)中遵循以下3個(gè)原則:

3) 帶有秘密參數(shù)的哈希函數(shù).若存在量子攻擊的可能性,推薦使用帶有秘密參數(shù)的哈希函數(shù).使用量子加密通信等可信信道來傳輸秘密參數(shù),利用量子物理特性來保證秘密參數(shù)的機(jī)密性,從而抵御經(jīng)典或量子計(jì)算機(jī)可能的攻擊.

4 結(jié) 語

本文對哈希函數(shù)的量子計(jì)算攻擊及其對區(qū)塊鏈的影響進(jìn)行了分析,對當(dāng)前的5類抗量子攻擊的區(qū)塊鏈中的哈希函數(shù)進(jìn)行了分析、對比和總結(jié),最后對區(qū)塊鏈中的哈希函數(shù)的設(shè)計(jì)給出了幾點(diǎn)建議,本文的工作將為后量子時(shí)代區(qū)塊鏈中的哈希函數(shù)的設(shè)計(jì)提供有益參考,下一步將針對量子時(shí)代的區(qū)塊鏈的特性和不足,提出新的抗量子設(shè)計(jì)方案,在輕量化、抗碰撞性、安全性上等取得更好的發(fā)展.