原文作者：Davide Castelvecchi
研究人員表示，雖然一種新算法可能還無(wú)法快速破解當(dāng)前的加密密鑰，但這不是我們自滿的理由。
一個(gè)中國(guó)團(tuán)隊(duì)揭示了一項(xiàng)新技術(shù)，該技術(shù)——理論上——可以用一臺(tái)很簡(jiǎn)單的量子計(jì)算機(jī)破解用來(lái)保護(hù)數(shù)字隱私的最常見(jiàn)技術(shù)。
研究團(tuán)隊(duì)稱(chēng)，這項(xiàng)技術(shù)成功完成了小規(guī)模演示，但其他專(zhuān)家懷疑這個(gè)程序擴(kuò)展后能否在該任務(wù)上打敗普通計(jì)算機(jī)。他們提醒道，這篇上個(gè)月發(fā)布在arXiv預(yù)印本服務(wù)器上的論文[1]再次提醒我們，網(wǎng)絡(luò)隱私有多么不堪一擊。
位于紐約IBM托馬斯·J·沃森研究中心的一臺(tái)量子計(jì)算機(jī)。來(lái)源：Connie Zhou for IBM
已知量子計(jì)算機(jī)會(huì)對(duì)當(dāng)前的加密系統(tǒng)構(gòu)成潛在威脅，但量子計(jì)算機(jī)的發(fā)展仍處于起步階段。研究人員普遍認(rèn)為，量子計(jì)算機(jī)破解密鑰的速度超過(guò)普通計(jì)算機(jī)還要等很多年。這里的密鑰是指用來(lái)保護(hù)數(shù)據(jù)的加密算法中的一串字符。
研究人員在1990年代就意識(shí)到，量子計(jì)算機(jī)可以利用物理學(xué)的一些奇異特性執(zhí)行“經(jīng)典”計(jì)算機(jī)無(wú)法完成的任務(wù)。如今就職于美國(guó)麻省理工學(xué)院的數(shù)學(xué)家Peter Shor在1994年證明[2]了如何利用量子疊加態(tài)（描述原子大小對(duì)象同時(shí)處于多種狀態(tài)的能力）和量子干涉（類(lèi)似于池塘里水波的相互疊加或抵消）的現(xiàn)象，將整數(shù)分解成素?cái)?shù)——素?cái)?shù)是無(wú)法進(jìn)一步分解成沒(méi)有余數(shù)的整數(shù)。
對(duì)于當(dāng)前保護(hù)網(wǎng)絡(luò)隱私和安全的常見(jiàn)加密技術(shù)以及一種基于大素?cái)?shù)的加密系統(tǒng)來(lái)說(shuō)，Shor的算法能讓量子計(jì)算機(jī)破解這些系統(tǒng)的速度遠(yuǎn)超經(jīng)典計(jì)算機(jī)，后一種基于大素?cái)?shù)的加密系統(tǒng)名為Rivest–Shamir–Adleman，以三位發(fā)明者的首字母命名，簡(jiǎn)稱(chēng)RSA。不過(guò)，Shor的技術(shù)需要一臺(tái)比現(xiàn)有原型機(jī)大很多倍的量子計(jì)算機(jī)。量子計(jì)算機(jī)的大小取決于量子比特（qubit）的數(shù)量。研究人員表示，破解RSA可能需要100萬(wàn)或以上的量子比特。當(dāng)前最大的量子計(jì)算機(jī)是IBM去年11月宣布的Osprey芯片，該芯片有433個(gè)量子比特。
新方法
北京量子信息科學(xué)研究院的魏世杰與合作者嘗試用另一種方法破解RSA，這種方法沒(méi)有用Shor算法，而是用了Schnorr算法。Claus Schnorr是德國(guó)法蘭克福大學(xué)的數(shù)學(xué)家，他也在1990年代設(shè)計(jì)出了一種分解整數(shù)的方法。Schnorr算法最初是為經(jīng)典計(jì)算機(jī)設(shè)計(jì)的，但魏世杰團(tuán)隊(duì)使用量子近似優(yōu)化算法（QAOA）在量子計(jì)算機(jī)上運(yùn)行了其中部分流程。
在這篇尚未經(jīng)過(guò)同行評(píng)審的論文中，作者稱(chēng)他們的算法只要372個(gè)量子比特就有望破解很強(qiáng)的RSA密鑰——這類(lèi)數(shù)字有600位以上的十進(jìn)制數(shù)。在代表全體作者寫(xiě)給《自然》的一封郵件中，清華大學(xué)物理學(xué)家龍桂魯提醒道，光靠增加量子比特是不夠的，當(dāng)前的量子計(jì)算機(jī)很容易出錯(cuò)，無(wú)法準(zhǔn)確進(jìn)行這么大的計(jì)算。“一味地增加量子比特?cái)?shù)目，卻不降低錯(cuò)誤率并無(wú)幫助。”
中國(guó)科學(xué)技術(shù)大學(xué)研制量子計(jì)算機(jī)的物理學(xué)家陸朝陽(yáng)未參與這項(xiàng)研究，他說(shuō)，在這么小的計(jì)算機(jī)上運(yùn)行QAOA算法需要這372個(gè)量子比特在99.9999%的時(shí)間里都能無(wú)錯(cuò)誤工作。而當(dāng)前最先進(jìn)的量子比特只能勉強(qiáng)達(dá)到99.9%的準(zhǔn)確率。
該團(tuán)隊(duì)在一臺(tái)10量子比特的量子計(jì)算機(jī)上演示了該技術(shù)，他們分解了一個(gè)較易操作的15位數(shù)字——261,980,999,226,229。（這個(gè)數(shù)字可以分解成兩個(gè)素?cái)?shù)，15,538,213×16,860,433。）研究團(tuán)隊(duì)表示，這是目前在量子計(jì)算機(jī)輔助下分解過(guò)的最大數(shù)字，但仍然比現(xiàn)代網(wǎng)頁(yè)瀏覽器使用的加密密鑰要小很多。
研究爭(zhēng)議
問(wèn)題在于，沒(méi)人知道QAOA是否能讓大數(shù)分解的速度比在筆記本電腦上單獨(dú)運(yùn)行Schnorr的經(jīng)典算法更快一些。作者寫(xiě)道，“需要指出的是，現(xiàn)在對(duì)該算法的量子加速還不清楚。”換句話說(shuō)，雖然Shor算法能確保在有足夠大的量子計(jì)算機(jī)的情況下快速破解加密，但這種基于優(yōu)化的技術(shù)也可以在小很多的機(jī)器上運(yùn)行，只是完成任務(wù)的時(shí)間可能會(huì)遙遙無(wú)期。
滑鐵盧大學(xué)數(shù)學(xué)家Michele Mosca也指出，QAOA不是第一個(gè)已知能用少數(shù)量子比特分解整數(shù)的量子算法。他與合作者在2017年描述過(guò)一個(gè)這種算法[3]。因此研究人員很清楚，沒(méi)有什么根本原因非得用很大的量子計(jì)算機(jī)才能分解數(shù)字。
其他研究人員也指出，雖然這篇最新論文可能是正確的，但它對(duì)速度的警告只出現(xiàn)在了論文末尾。得克薩斯大學(xué)奧斯汀分校的量子計(jì)算理論學(xué)家Scott Aaronson在他的博客中寫(xiě)道，“總而言之，這是我在過(guò)去25年里看到的最誤導(dǎo)人的量子計(jì)算論文。”
龍桂魯在郵件中表示，他與合作者打算修改論文，把警告部分提到前面來(lái)。郵件中還寫(xiě)道，“我們歡迎同行的評(píng)審，也愿意與全球科學(xué)家交流。”
就算這項(xiàng)基于Schnorr 算法的技術(shù)無(wú)法攻克互聯(lián)網(wǎng)，量子計(jì)算機(jī)也可能通過(guò)運(yùn)行Shor算法最終實(shí)現(xiàn)這一步。安全研究員一直在設(shè)計(jì)各種被認(rèn)為不易受量子攻擊的替代加密系統(tǒng)，這類(lèi)系統(tǒng)被稱(chēng)為后量子（post-quantum）或量子安全（quantum-safe）。當(dāng)然，研究人員今后可能會(huì)發(fā)現(xiàn)打敗這些系統(tǒng)的量子算法，造成不堪設(shè)想的后果。
“對(duì)于數(shù)字基礎(chǔ)設(shè)施的信心可能會(huì)崩塌，”Mosca說(shuō)，“我們對(duì)量子安全遷移的管理將從技術(shù)生命周期管理突然過(guò)渡到危機(jī)管理，”他說(shuō)，“到時(shí)候無(wú)論從哪方面看都會(huì)很糟。”
參考文獻(xiàn)：
1. Yan, B.et al. Preprint at https://arxiv.org/abs/2212.12372 (2022).
2. Shor, P. W.Phys. Rev. A52, R2493–R2496 (1995).
3. Bernstein, D. J., Biasse, J.-F. & Mosca, M. inPost-Quantum CryptographyVol. 10346 (eds Lange, T. & Takagi, T.) 330–346 (Springer, 2017).
原文以Historic US research strike ends — but energizes a movement標(biāo)題發(fā)表在2022年1月12日《自然》的新聞版塊上
