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