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