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