量子計算與密碼學
二十世紀后期，美國學者提出了基于量子計算機的質因數分解算法——Shor算法，從理論上證明，在當前最快的計算機上需要上萬年才能完成的計算任務，量子計算機瞬間即能完成，嚴重地威脅到了基于這類數學難題的公鑰密碼系統的安全性。緊隨其后的Grover量子搜索算法，對于密碼破譯來說，相當于把密鑰的長度減少一半，種種跡象表明，通用量子計算機一旦實現，對目前廣泛使用的RSA、EIGamal、ECC公鑰密碼和DH密鑰協商協議都構成了嚴重的威脅。隨著量子技術的不斷成熟，實用量子計算機總會有到來的一天，到了那一天，密碼學，特別是基于NP困難問題的公鑰密碼系統又該做何準備呢?現在的量子計算機具有怎樣的能力?研制量子計算機的困難是什么?真正的量子計算機離我們還有多遠?
首先，我們回顧量子計算機研制的歷史：
量子計算機研究進展及關鍵問題
量子計算機研制過程中的里程碑事件
- 2001年IBM研制出7個量子位的示例型量子計算機，向世界宣布了量子計算機原理的可行性。
- 2011年9月2日，美國加州大學圣塔芭芭拉分校的科學家宣布，研制出具有馮諾依曼計算機結構的量子計算機并成功地進行了小合數的因子分解實驗。
- 2013年3月1日IBM宣布找到了一種可以大規模提升量子計算機量子位數的關鍵技術。
- 2015年谷歌、美國國家航空航天局(NASA)和加州大學圣塔芭芭拉分校(UCSB)公開報道，實現了九個超導量子比特的操縱。
- 2017年5月3日，中國科學院在上海召開新聞發布會，宣布世界首臺超越早期經典計算機的光量子計算機在我國誕生。在光學體系方面，研究團隊在2016年首次實現十光子糾纏操縱的基礎上，利用高品質量子點單光子源構建了世界首臺超越早期經典計算機的單光子量子計算機。
十超導量子比特的糾纏態
基于單光子的量子計算原型機結構
國際上最高品質和最高效率的單光子源
量子計算的目標在于打造一款通用的量子計算機——不僅能夠解決任何運算問題，而且其速度更超越當今最快的超級計算機，為了更早地讓量子計算機展現出它的優勢，物理學家們想到了針對一些特殊的問題，可以用專用量子計算機來解決，如加拿大D-wave System的專用量子計算機，可用于解決優化的問題，可執行Grover算法。2007年2月D- Wave公司宣布研制出世界上第一臺商用16量子位的量子計算機，2008年5月提高到48量子位,2011年5月30日又提高到了128量子位,2013年初又提高到了512量子位。
量子技術主要研究內容
建造量子計算機的困難在于要找到一個可以編碼量子比特，滿足Divincenzo判據，包括具有可擴展性、可初始化、可讀出、相干時間長、可構造普適量子邏輯門、可網絡化等。其中可擴展性和相干時間長是選擇物理實現系統的兩項重要指標。根據DARPA的量子信息科學技術路線圖和《歐洲量子信息處理與通信研究現狀、遠景與目標戰略報告》，現在確定的主要物理實現系統有量子點、超導量子電路、離子阱體系、腔量子電動力學體系、光學體系、液態核磁共振、固態量子計算等量子計算的物理實現方案。其中超導量子電路方案是利用了超導體中的約瑟夫森結來產生量子比特，因為其具有良好的可擴展性，成為量子計算機物理實現系統的研究熱點。
量子計算機的為什么具有超級計算能力?
簡單地講，量子計算機利用量子力學中的疊加態原理，量子計算最大的特性就是并行性，當量子計算機對一個n量子比特的數據進行處理時，量子計算機實際上是同時對2的n次方個數據狀態進行了處理。正是這種并行性使得原來在電子計算機環境下的一些困難問題在量子計算機環境下變得容易。量子計算機的這種超強計算能力，使得基于計算復雜度的現有公鑰密碼的安全受到挑戰。
量子計算機離我們有多遠?
為提高量子計算機的計算能力，需要把量子比特都耦合起來，這一難度是指數級的。2016年，Gartner預測量子計算機技術將超過10年才能成熟(如圖所示)。
Gartner預測2016年新興科技技術成熟度曲線
與經典計算機計算能力相比，當量子計算機操縱25個量子的時候，其計算能力相當于現有的計算機四核計算能力，而當量子計算機能操縱50個量子的時候，其計算能力將超過現在世界上最快的計算機——天河二號。
抗量子計算公鑰密碼體制
量子計算機的每一步進展都為我們帶來了驚喜，同時也帶來了擔憂。經典密碼算法面臨的危機是客觀存在的。面對量子計算機的潛在威脅，如何設計能夠抵御量子計算攻擊的密碼算法值得我們深入研究。現代密碼學是建立在計算復雜性理論基礎之上的。例如，RSA公鑰密碼體制的構造基礎是大整數因子分解這一NP問題，然而在量子計算機上分解大整數在量子圖靈機環境下是可解的，不再是難題。量子計算對現代密碼學的威脅實質就是依賴于量子計算機的高度并行計算能力，將相應的NP問題轉化成了QP問題，這對于基于NP問題設計的現代公鑰密碼而言，其潛在的威脅是致命的。
量子算對傳統密碼算法的沖擊
雖然今天的量子計算能力還不足以真正撼動現有密碼系統，但隨著量子計算技術的發展，總會有一天對現有的密碼構成實際威脅。為應對量子計算機的挑戰，美國國家標準局NIST(National Institute of Standards and Technology)在2016年2月召開的“后量子密碼”(Post Quantum Cryptography )會議上發布“抗量子計算密碼：NIST未來研究計劃”報告，征集后量子密碼方案，并將其作為今后抗量子計算攻擊的標準，對于方案在算法實現上要求具備參數可調和、使用平臺多樣化，其中算法抗側信道攻擊也是一項重要的指標。
事實上，對于某些問題(如NP完全問題)，量子算法相對于傳統算法并沒有明顯的優勢。緊跟著Shor算法的出現，國內外密碼學家已對基于格、基于編碼和基于多變元方程密碼方案展開了大量的研究，力圖設計可以對抗量子計算機的經典密碼算法，同時也在不斷設計新的抗量子計算密碼方案。
經過二十多年的發展，越來越多的量子計算領域的科學家意識到，實用的量子計算機不再僅僅存在于理論之中，盡管可能造價不菲、技術難度很高，但是制造一臺實用的量子計算機現在更多地成為一個工程問題，在通用量子計算機出現之前，密碼學家將積極準備好新的更安全的抗量子計算密碼算法，保障人們各種活動的信息安全，迎接量子時代的到來。
【本文為51CTO專欄作者“中國保密協會科學技術分會”原創稿件，轉載請聯系原作者】
