量子計算與區(qū)塊鏈是當下兩個熱門技術，二者因為密碼學技術聯(lián)系在一起。區(qū)塊鏈使用密碼學技術保障系統(tǒng)安全，而量子計算對傳統(tǒng)的密碼學技術提出了巨大的挑戰(zhàn)，進而威脅到區(qū)塊鏈系統(tǒng)的安全。

目前對量子計算的認識有兩個極端，一種觀點是量子計算無所不能，第二種觀點是量子計算還很遙遠。量子計算可以做哪些事情？對傳統(tǒng)密碼體制有哪些安全威脅？

對這些問題的把握可以從兩個方面入手：

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

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

區(qū)塊鏈是一個去中心化的分布式記賬系統(tǒng)，采用密碼學技術保護賬本不被篡改和實現(xiàn)節(jié)點共識。我們以OKChain（OK公鏈）為例，區(qū)塊鏈系統(tǒng)中的主要密碼學應用包括：

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

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

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

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

目前常見的量子算法主要基于Simon算法、Shor算法和Grover算法。

1、Simon算法用于求解周期計算（finding period）問題。若一個函數(shù)為周期函數(shù)，則Simon算法可以在多項式時間內計算得到該周期。

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

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

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

針對Hash函數(shù)等對稱密碼體制，量子計算目前沒有有效的攻擊方法?？沽孔用艽a體制研究集中在公鑰密鑰和數(shù)字簽名方案領域。

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

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

（2）該困難問題是NP-hard的。

2012年，美國國家標準與技術研究院（NIST）啟動了后量子密碼的標準化并于2016年開始向全世界公開征集后量子算法。截止到2017年11月30日，NIST共收到各種后量子時代公鑰密碼方案82項。

目前主要有四類算法：

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

2、基于多變元多項式的密碼體制。該類算法基于多變元方程求解的困難性設計，如Rainbow數(shù)字簽名方案。

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

4、基于編碼問題的密碼體制。該類密碼基于糾錯碼設計，隨機線性糾錯碼求解問題已經被證明是NP-hard的。代表性密碼如McEliece密碼體制。

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

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