量子計(jì)算與區(qū)塊鏈?zhǔn)钱?dāng)下兩個(gè)熱門技術(shù)，二者因?yàn)槊艽a學(xué)技術(shù)聯(lián)系在一起。區(qū)塊鏈?zhǔn)褂妹艽a學(xué)技術(shù)保障系統(tǒng)安全，而量子計(jì)算對(duì)傳統(tǒng)的密碼學(xué)技術(shù)提出了巨大的挑戰(zhàn)，進(jìn)而威脅到區(qū)塊鏈系統(tǒng)的安全。

目前對(duì)量子計(jì)算的認(rèn)識(shí)有兩個(gè)極端，一種觀點(diǎn)是量子計(jì)算無(wú)所不能，第二種觀點(diǎn)是量子計(jì)算還很遙遠(yuǎn)。量子計(jì)算可以做哪些事情？對(duì)傳統(tǒng)密碼體制有哪些安全威脅？

對(duì)這些問(wèn)題的把握可以從兩個(gè)方面入手：

（1）區(qū)塊鏈系統(tǒng)采用的密碼學(xué)技術(shù)；

（2）量子計(jì)算對(duì)傳統(tǒng)密碼體制的威脅；

區(qū)塊鏈?zhǔn)且粋€(gè)去中心化的分布式記賬系統(tǒng)，采用密碼學(xué)技術(shù)保護(hù)賬本不被篡改和實(shí)現(xiàn)節(jié)點(diǎn)共識(shí)。我們以O(shè)KChain（OK公鏈）為例，區(qū)塊鏈系統(tǒng)中的主要密碼學(xué)應(yīng)用包括：

1、哈希函數(shù)用于PoW計(jì)算。哈希函數(shù)為系統(tǒng)提供“單向性”：正向計(jì)算很容易，逆向求解很困難。在傳統(tǒng)的PoW中，找到一個(gè)符合條件的原象（挖礦）需要一定的算力保證，但驗(yàn)證一個(gè)解是容易的。

2、簽名與多簽技術(shù)。經(jīng)典的簽名方案有EC-Schnorr和ECDSA，主要基于ECC上的CDH問(wèn)題設(shè)計(jì)，即假設(shè)CDH問(wèn)題在數(shù)學(xué)上是困難的，則密碼體制是安全的。OKChain采用了更加高效的BLS多簽方案。

3、可驗(yàn)證隨機(jī)函數(shù)（VRF）?；赩RF，OKChain系統(tǒng)中采用了可驗(yàn)證隨機(jī)洗牌函數(shù)（VRSF），用于共識(shí)決定出塊者優(yōu)先級(jí)序列。

量子計(jì)算突破了傳統(tǒng)計(jì)算的極限，在求解一些重要密碼問(wèn)題上獲得了指數(shù)加速，對(duì)現(xiàn)有密碼體制的安全性提出了極大的挑戰(zhàn)。但量子計(jì)算不是萬(wàn)能的，也不是對(duì)所有問(wèn)題都可以有多項(xiàng)式時(shí)間算法。

目前常見(jiàn)的量子算法主要基于Simon算法、Shor算法和Grover算法。

1、Simon算法用于求解周期計(jì)算（finding period）問(wèn)題。若一個(gè)函數(shù)為周期函數(shù)，則Simon算法可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算得到該周期。

2、Shor算法用于求解整數(shù)分解（integer factoring）問(wèn)題，該算法為多項(xiàng)式時(shí)間算法。由于DH問(wèn)題與整數(shù)分解問(wèn)題在多項(xiàng)式時(shí)間內(nèi)可以相互轉(zhuǎn)化，所以DH體制以及ECC上的DH體制在多項(xiàng)式時(shí)間內(nèi)都可以在量子機(jī)上求解。

3、Grover算法可以在一個(gè)無(wú)序的數(shù)據(jù)庫(kù)中查找符合條件的解（即窮搜），相較于經(jīng)典遍歷窮搜可以獲得平方加速。

現(xiàn)有很多簽名方案如RSA和ECDSA的安全假設(shè)是CDH（computational Diffie–Hellman）問(wèn)題是困難的。目前對(duì)量子攻擊的擔(dān)心主要來(lái)源于Shor算法對(duì)RSA、DH等密碼問(wèn)題的求解，進(jìn)而威脅到包括BLS在內(nèi)的大多數(shù)簽名方案的安全。

針對(duì)Hash函數(shù)等對(duì)稱密碼體制，量子計(jì)算目前沒(méi)有有效的攻擊方法。抗量子密碼體制研究集中在公鑰密鑰和數(shù)字簽名方案領(lǐng)域。

由于量子計(jì)算對(duì)傳統(tǒng)密碼體制的威脅，抗量子（后量子）密碼體制逐漸被提出并標(biāo)準(zhǔn)化?，F(xiàn)階段，所謂的密碼體制抗量子一般包括兩個(gè)方面：

（1）該加密體制可以規(guī)約到一個(gè)困難數(shù)學(xué)問(wèn)題上；

（2）該困難問(wèn)題是NP-hard的。

2012年，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）啟動(dòng)了后量子密碼的標(biāo)準(zhǔn)化并于2016年開(kāi)始向全世界公開(kāi)征集后量子算法。截止到2017年11月30日，NIST共收到各種后量子時(shí)代公鑰密碼方案82項(xiàng)。

目前主要有四類算法：

1、基于格困難問(wèn)題的密碼體制。該類密碼算法基于格上的最短向量（SVP）等困難問(wèn)題設(shè)計(jì)，如NTRU密碼。

2、基于多變?cè)囗?xiàng)式的密碼體制。該類算法基于多變?cè)匠糖蠼獾睦щy性設(shè)計(jì)，如Rainbow數(shù)字簽名方案。

3、基于哈希函數(shù)的數(shù)字簽名方案。該類密碼基于Hash函數(shù)的安全性設(shè)計(jì)，如Merkle簽名方案。

4、基于編碼問(wèn)題的密碼體制。該類密碼基于糾錯(cuò)碼設(shè)計(jì)，隨機(jī)線性糾錯(cuò)碼求解問(wèn)題已經(jīng)被證明是NP-hard的。代表性密碼如McEliece密碼體制。

鑒于量子計(jì)算帶來(lái)的安全隱患，已經(jīng)有團(tuán)隊(duì)開(kāi)展抗量子的區(qū)塊鏈體制研究，如ZK-STARK系統(tǒng)。ZK-STARK系統(tǒng)采用了基于Hash函數(shù)的數(shù)字簽名方案來(lái)替代基于CDH假設(shè)的數(shù)字簽名方案，從而可以抵抗量子攻擊。

OK區(qū)塊鏈工程院在抗量子計(jì)算和可證明安全等領(lǐng)域已經(jīng)開(kāi)展了基礎(chǔ)研究，將為用戶提供安全、高效的區(qū)塊鏈解決方案。