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

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

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

（1）區塊鏈系統采用的密碼學技術；

（2）量子計算對傳統密碼體制的威脅；

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

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

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

3、可驗證隨機函數（VRF）。基于VRF，OKChain系統中采用了可驗證隨機洗牌函數（VRSF），用于共識決定出塊者優先級序列。

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

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

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

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

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

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

針對Hash函數等對稱密碼體制，量子計算目前沒有有效的攻擊方法。抗量子密碼體制研究集中在公鑰密鑰和數字簽名方案領域。

由于量子計算對傳統密碼體制的威脅，抗量子（后量子）密碼體制逐漸被提出并標準化。現階段，所謂的密碼體制抗量子一般包括兩個方面：

（1）該加密體制可以規約到一個困難數學問題上；

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

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

目前主要有四類算法：

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

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

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

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

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

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