數學家Peter Shor：量子計算機威脅網絡加密，只是時間

2020-12-15 知識分子

以下文章來源於Nature自然科研 ，作者Nature自然科研。


應用數學家Peter Shor解決了量子計算領域的一個重要問題。來源：BBVA FOUNDATION


最近，中國科學技術大學潘建偉、陸朝陽團隊構建的一套光量子計算系統，在高斯玻色採樣問題上實現量子優越性，求解速度達到目前全球最快的超級計算機的一百萬億倍，遠遠超過經典計算機。
而在25年前，美國應用數學家Peter Shor提出Shor算法，證明了如何讓量子計算變得可行，量子計算會如何威脅到數據。


撰文 | Davide Castelvecchi


● 　● 　●


上世紀80年代，當物理學家首次提出量子計算機的想法時，它們聽起來就像是理論上很精彩、但可能註定只能停留在論文裡的概念。到了1995年，也就是25年前的10月，數學家 Peter Shor 發表的一篇論文 [1] 改變了人們的看法。


Shor在論文中證明了如何克服量子計算機的一個關鍵問題。量子計算機以量子比特為單位處理信息——量子比特對應經典比特，但能同時表示0和1。已知量子態對噪聲非常敏感，這會造成信息丟失。Shor提出的誤差修正技術能檢測到噪聲導致的錯誤，帶來了一種讓量子信息更抗噪的方法。


Shor目前就職於麻省理工學院，同時也是一位出版過作品的詩人。1994年，他第一次發現了 [2] 使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。


如今，量子計算機已經成為現實，但它們分解超過兩位數數字的能力依然處於初級水平。但是，量子計算機威脅到網絡加密只是一個時間問題。


最近，Shor在接受《自然》雜誌採訪時，就如何看待自己研究的影響力，網絡安全的未來將走向何方等分享了自己的看法。


在你的分解質因數算法出現前，量子計算機是否只停留在理論層面？


我的論文確實給了大家一種印象，就是這些計算機能做些有用的事。計算機科學家 Daniel Simon 在我的結果出來前，解決了他遇到的一個問題，證明了量子計算機（比普通計算機）快了好幾個指數級。但即使有了 Simon 的算法，人們依然不清楚量子計算機能有什麼用。


你公布這個分解質因數算法時，人們有何反應？


剛開始，我只得到了中間結果。1994年4月，我在[當時我就職的新澤西州]貝爾實驗室（Bell Labs）做了一次關於它的演講。消息傳得很快，那個周末，計算機科學家 Umesh Vazirani 給我打了個電話。他說：「我聽說你能用量子計算機分解質因數，請告訴我是如何做到的。」 那時候，我其實還沒有解決分解質因數的問題。我不知道你聽說過兒童遊戲 「打電話」 沒有，但不知怎的，五天時間裡，我的研究結果就變成了分解質因數，因為人們都在這樣傳。在那五天裡，我正好也解決了那個問題，所以我能告訴Umesh如何做。


我的論文還沒寫完的時候，就有各種各樣的人來問我要論文，所以我只能把還不完整的草稿先寄給他們。


但是許多專家還是認為量子計算機會在完成計算前丟失信息？


有一個反對意見是說在量子力學中，如果你測量一個系統，你就會不可避免地幹擾它。我證明了如何在測量錯誤的同時不測量計算，這樣你就能糾正錯誤，而不會破壞整個計算。


在我那篇1995的糾錯論文發表後，一些懷疑人士也開始相信量子計算或許是可行的。


糾錯依賴 「物理」 和 「邏輯」 量子比特。這兩者有什麼差別？


為量子計算機寫算法時，假設的是量子比特是無噪的，算法中描述的這些無噪量子比特就是邏輯量子比特。實際上量子計算機中沒有無噪量子比特，事實是，如果我們在不進行任何降噪的情況下運行算法，幾乎必定會出現錯誤。


物理量子比特是量子計算機的其中一種噪聲量子比特。如果要在不出錯的情況下運行算法，我們就要利用物理量子比特編碼邏輯量子比特，使用一種量子糾錯碼。據我們所知，實現這一步的最好做法要求相當高—— 每個邏輯量子比特都需要許多物理量子比特。


要計算出這項技術需要多少量子比特是一項非常複雜的工作。如果你想用表面碼（目前最好的候選對象）構建一個量子計算機，每個邏輯量子比特大約需要100個物理量子比特或更多。


2019年，谷歌用54量子比特的量子計算機解決了一個經典計算機幾乎不可能完成的任務，這也是對 「量子優越性」 的首次演示。您對此有何評價？


它肯定是一個裡程碑。它表明了量子計算機可以比經典計算機做得更好—— 至少是在一些人為設計的問題上。谷歌確實進行了一些宣傳。但他們也有一臺非常值得稱道的量子計算機。但這個計算機依然需要改進，才能做出有意思的事來。還有初創公司IonQ，他們看起來好像能構建一個在某種程度上超過谷歌或IBM的量子計算機。


如果量子計算機能做大數質因數分解，它們就能破解 「RSA」 ——無處不在的網絡加密系統。


是的，但是最先破解RSA的人不是來自NSA（美國國家安全局），就是來自其他大型機構。這些計算機一開始會很慢。比如，如果你有一臺只能一小時破解一個RSA密鑰的計算機，那麼任何不屬於優先事項或國家安全風險的東西都不會被破解。相比看你的郵件，NSA的量子計算機有更重要的事情要做。


有沒有能取代RSA的密碼系統，即使在量子計算機時代（「後量子密碼」）也是安全的？


我認為已經有能取代RSA的後量子密碼系統了。RSA不是現在的大問題，現在的大問題是還有其他方法可以破壞網絡安全，比如惡意編程的軟體、病毒、向並非絕對誠實的一方發送信息等。我認為用安全的後量子密碼系統取代RSA的唯一阻礙是意志和編程時間。我認為我們已經知道要如何做到這一點，只是不清楚是否能及時做到。


我們是否有被突然襲擊的風險？


是的，人們已經為解決千年蟲問題（Year 2000）投入了大量精力。你需要付出大量努力才能過渡到後量子時代。如果我們等得太久，就太遲了。


原文以Quantum-computing pioneer warns of complacency over Internet security 為標題發表在 2020年10月30日的《自然》的News Q&A版塊上，《知識分子》獲授權轉載中文譯文。


參考文獻：

1. Shor, P. W. Phys. Rev. A 52, R2493(R) (1995).

2. Shor, P. W. Proc. 35th Annual Symp. Found. Comp. Sci. 124–134 (1994).

相關焦點

  • Peter Shor：量子計算機威脅到網絡加密只是時間問題
    ，同時也表明了量子計算會如何威脅到數據；以下是《自然》對他的採訪。1994年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。
  • 對話Peter Shor:量子計算機威脅到網絡加密只是一個時間問題
    到了1995年，也就是25年前的10月，數學家Peter Shor發表的一篇論文改變了人們的看法。1994年，他第一次發現了使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 量子計算機威脅到網絡加密只是一個時間問題|對話應用數學家Peter...
    25年前，Peter Shor證明了如何讓量子計算變得可行，同時也表明了量子計算會如何威脅到數據；以下是《自然》對他的採訪。1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 量子計算機威脅到網絡加密只是一個時間問題
    應用數學家 Peter Shor 解決了量子計算領域的一個重要問題。1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 九章量子計算機可以破解網絡密碼嗎？美國會怎樣應對我國量子崛起
    二、公鑰密碼業界一直流傳一個說法，量子計算機將會讓現有的網絡公鑰加密系統失效所謂公鑰加密，簡單來說，就是用一個公開的數學難題來給網絡傳遞的信息加密，題雖然知道，但答案不知道，所以就算把網絡信息截取下來，也無法破解人家說的是啥。但接收的那個人電腦裡就有密碼，直接就可以破解信息。這個數學難題擺在明面上，我們沒有答案靠自己算是算不出來的，就算用現在最先進的超級計算機，也得計算幾億年才行。
  • 抗量子加密:為什麼你迫切需要它
    你的組織必須防範來自不同來源的網絡威脅，例如有組織犯罪集團，民族黑客和個人黑客。許多組織依靠加密來保護自己。 毫無疑問，數百年來人們一直在使用各種形式的密碼。已使用的密碼示例包括古埃及將近4000年建造的墓牆中的非標準象形文字和阿拉伯數學家Al-Kindi於1200年前開發的替代密碼。
  • 量子計算機將威脅網際網路安全基礎的不對稱加密算法
    （量子計算機的性能超越所有傳統計算機），在其自研的量子計算機上用時3分20秒完成的任務需要最強超算運算1萬年，但隨後谷歌提交給NASA的論文後被刪除。上周的2019雲棲大會上，阿里達摩院就有一個宣布，就是其量子實驗室宣布完成了第一個可控的量子比特研發工作。那麼，性能強大的量子計算什麼時候能夠破解密碼？結論是：量子計算對諸如RSA和ECC這樣的不對稱密碼算法構成了生存威脅，這些算法實際上是當前所有網際網路安全的基礎。這個結論來自美國國家科學院量子計算可行性和含義的技術評估委員會。
  • 量子計算機刷屏,量子計算到底是什麼!
    △ 量子計算機對數據安全造成了巨大的威脅。（圖片來源：BGR）舉個例子，量子計算機可以輕而易舉的就破解信息安全機制。當這個數字的位數（在二進位下）足夠多時，這個分解的過程就變得不可能，數據加密就無法被解密。但如果應用基於量子計算邏輯的 shor's algorithm（見下文），整個分解的過程就會被縮減位log₂N量級的運算次數，這就意味著目前最安全的加密方式，幾分鐘就可以破解，而經典計算機可能需要永遠。但通過量子計算機，迅速破解信用卡、國家機密和其它機密資料都不在話下。
  • 什麼是後量子密碼學?保護數據免受量子計算機威脅的競賽正在展開
    HTTPS是一種網絡協議，對我們通過網際網路發送的數據和接收到的響應進行加密。這種加密和其他形式的加密一道保護著各種電子通信，諸如密碼、數字籤名和健康記錄等內容。量子計算機可以破壞這些密碼防禦能力。雖然量子計算機現在還不夠強大，但它們正在快速發展。十多年後，或者更短的時間內，量子計算機可能會對目前廣泛使用的加密方法構成威脅。
  • 量子機威脅現代計算機,未來如何保證加密安全?
    量子機威脅現代計算機，未來如何保證加密安全？ 中金網 發表於 2021-01-07 14:50:05 現代密碼學仍然是一門相對年輕的科學學科，但其歷史顯示出一種重要的模式。
  • 後量子加密究竟是什麼?
    目前，整個網際網路行業都在使用HTTPS以及其它一些形式的加密機制保護各類電子通信、密碼、數字籤名以及健康記錄等信息。量子計算機則可能很快摧毀這些加密防禦體系。雖然目前的量子計算機還遠稱不上強大，但其正在快速發展當中。有可能在未來十多年——甚至更短時間——之內，量子計算機就會給目前廣泛使用的加密方法構成巨大威脅。
  • 「思考」量子威脅當前 未來如何保證加密安全?
    同樣，最近用於保護私鑰或密封投標拍賣的多方計算(MPC)的部署也使用了大約在同一時間開發的思想。現在，隨著量子機的威脅籠罩在現代計算機上，對更新、更強的密碼學形式的需求從未如此強烈。沒有人確切地知道量子計算機何時或是否會被證明有能力破解今天的加密方法。然而，僅僅是威脅本身就促使人們在開發替代方案方面做了大量的工作，這些替代方案將被證明足夠強大，能夠抵禦量子攻擊。
  • 「量子計算」量子計算會使加密技術過時，量子網際網路是解決方案
    自世紀之交以來，沒有任何一個商業組織比它更直接地參與到未來量子計算機網絡的科學發展和工作理論中。有一類理論涉及加密安全性。一旦量子計算機(QC)突破了目前由公鑰加密技術(PKC)控制的大壩，世界上的每一條加密信息都將受到攻擊。這就是赫特納的「量子威脅」。
  • 擔憂中國量子科技優勢，美國計劃構建抗量子密碼體系
    圖片來源：USTC早在1994年量子計算理論發展的初期，美國數學家Peter Shor就提出了讓量子計算變得可行的Shor大數分解算法，這讓量子計算機威脅到網絡加密只是一個時間問題。去年9月，谷歌團隊利用一個53比特的超導量子計算機，首次實現量子霸權。他們在200秒的時間內解決了一個超級計算機SUMMIT需要耗時一萬年才能完成的任務。中國作為全球量子計算賽道的主要玩家自然不甘落後。今年12月4日，中科大團隊宣布利用光量子計算原型機「九章」實現量子霸權，並且所處理問題的速度比超級計算機「富嶽」要快100萬億倍。
  • 未來的量子計算機將在8小時內破解2048位RSA加密
    毫無疑問，許多人擔心量子計算機將能夠破解全球最流行的加密技術中的70％以上，使它們變得無用和過時，並將他們保護的敏感數據暴露給任何想要讀取的人。但是，主要的加密技術是使用所謂的「活板門」數學函數對數據進行加密的技術，這些函數可以在一個方向上輕鬆地工作，而在另一個方向上卻不行。
  • 科普問答 | 現有的量子計算機能否破解rsa等商用軍用加密技術?
    群友問：現有的量子計算機能否破解rsa等商用軍用加密技術?實用型的通用量子計算機能做出嗎?如果不能，是因為計算原理導致的嗎?如果沒有發明好的算法，量子計算機的表現可能與傳統計算機無異，甚至更差。之所以量子計算機被認為能夠破解RSA加密算法，正是因為彼得·秀爾在貝爾實驗室工作期間提出了量子質因數分解算法（也稱秀爾算法）。(Shor算法——以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子算法(在量子計算機上面運作的算法)。
  • 美國防大學《稜鏡》雜誌發文分析 量子計算對美國家安全構成的網絡威脅
    編者按量子計算既會對國家安全產生網絡威脅，也存在潛在的戰略優勢。量子計算將推動生物學、化學、物理學等諸多學科的科技進步，但在網絡安全領域，也可被對手國家用於破解公共密碼系統。從理論上講，量子雖存在但還未實際應用，建造大型量子計算機面臨誤差導致的振動、電磁波和溫度波動等各種工程挑戰。目前使用的RSA和「橢圓曲線」主要公鑰算法，被認為易受量子攻擊。科學家預測，研究人員需在未來20年內克服以上挑戰，才能使量子計算機破解目前使用的主流公鑰方案。
  • 什麼是量子密碼學?RSA加密算法又是什麼?量子計算機厲害嗎?
    」是一門通過量子計算機強大的計算能力進行加密/解密的新興學科。確實，破解1024位長的RSA算法，傳統的計算機可能需要幾十萬年，而用一臺512個量子比特（qubits）的量子計算機理論上可以做到1秒破解。隨著密鑰位長的增加，破解難度急速增加。
  • 量子計算機無用？美針對九章研討，如何抵禦「量子威脅」引發熱議
    中國近日在量子計算機上取得的突破令全世界側目，中國量子計算機以超乎尋常的能力實現了「量子霸權」，但是就在全國都為這一成就歡呼的時候，有的人卻質疑，量子計算機到底有什麼用？聽起來很厲害，但是根本不能為國家軍事或者我們的生活起到什麼實際性的作用。面對這種質疑，美國最近的舉動給出了他們的解答。
  • 量子計算機能做什麼用途？
    但「特定問題」只是一些毫無價值的問題，量子計算機作為一個工具，它將來究竟能為我們做些什麼有用的事情呢？其實，量子計算機的誕生與兩個實際問題密切相關——模擬量子系統裡的物理過程、破解密碼。而且由於其強大的計算能力，量子計算機誕生之初，就有科學家就證明了量子計算機在大量數據的搜索方面也有巨大的優勢。