三週前，恐慌席捲了安全世界的某些角落，因為研究人員發現了一項突破，終於將破解廣泛使用的 RSA加密 通過使用量子計算，方案觸手可及。
二十年前，科學家和密碼學家就已經知道，一種被稱為 Shor 算法的因式分解方法使具有足夠資源的量子計算機在理論上有可能破解 RSA。 這是因為支撐 RSA 密鑰安全性的秘密質數很容易使用 Shor 算法計算出來。 使用經典計算計算相同的素數需要數十億年。
唯一阻礙這種世界末日場景的是 Shor 算法破解足夠大的 RSA 密鑰所需的大量計算資源。 目前的估計是，破解 1,024 位或 2,048 位的 RSA 密鑰需要一台擁有大量資源的量子計算機。 具體來說，這些資源大約有 2000 萬個量子位，其中大約有 8 個小時以疊加方式運行。 （量子位是量子計算的基本單位，類似於經典計算中的二進制位。但是經典二進制位只能表示單個二進制值，例如 0 或 1，而量子位由多個可能的疊加表示狀態。）
這 紙，三週前由中國的一組研究人員發表，報告發現了一種分解方法，該方法可以使用僅具有 372 個量子位的量子系統在使用數千個操作步驟運行時破解 2,048 位 RSA 密鑰。 這一發現如果屬實，將意味著 RSA 加密技術向量子計算的衰落可能比大多數人認為的要早得多。
RSA 的消亡被大大夸大了
週二在加利福尼亞州聖克拉拉舉行的 Enigma 2023 會議上，計算機科學家和安全與隱私專家 Simson Garfinkel 向研究人員保證，RSA 的消亡被大大夸大了。 他說，目前，量子計算幾乎沒有實際應用。
“在短期內，量子計算機有一個好處，那就是在著名期刊上發表論文，”Garfinkel 與 Chris Hoofnagle 合著了 2021 年的書 量子時代的法律和政策，告訴觀眾。 “他們相當擅長的第二件事，但我們不知道還能持續多久，就是他們相當擅長獲得資金。”
即使量子計算變得足夠先進以提供有用的應用程序，這些應用程序也可能用於模擬物理和化學，以及執行經典計算無法很好工作的計算機優化。 加芬克爾表示，在可預見的未來，有用應用的匱乏可能會帶來“量子冬天”，類似於 AI 最終起飛前的多輪人工智能冬天。
本月早些時候發表的論文的問題在於它依賴於 1994 年開發的 Schnorr 算法（不要與 Shor 算法混淆）。Schnorr 算法是一種基於格的經典計算，格是一種數學結構，在許多領域都有應用建設性密碼學和密碼分析。 設計 Schnorr 算法的作者表示，它可以增強啟發式量子優化方法的使用，稱為 質量保證書.
在短時間內，許多研究人員指出 致命缺陷 在 Schnorr 的算法中幾乎揭穿了它。 具體來說，批評者表示，沒有證據支持作者關於 Schnorr 算法實現多項式時間的說法，而不是經典算法實現的指數時間。
三週前的研究論文似乎從表面上理解了 Shor 的算法。 即使據說使用 QAOA 對其進行了增強（目前尚無支持），它是否能提供任何性能提升也值得懷疑。
“總而言之，這是我 25 年來見過的最具誤導性的量子計算論文之一，而且我見過……很多，”德克薩斯大學奧斯汀分校的計算機科學家兼量子計算主任 Scott Aaronson信息中心， 寫了. “話雖如此，這實際上並不是我第一次遇到這樣一個奇怪的想法，即我們從 Shor 算法中了解到的整數因式分解的指數量子加速應該以某種方式‘擦掉’到不包含任何東西的量子優化啟發式上秀爾算法的實際見解，就像是通過同情魔法。”