密碼學家發現了量子保密的新基石

讓我們假設你想發送一條私密信息、進行秘密投票或是安全地簽署文件。如果你在電腦上執行這些任務，就需要依靠加密來保證數據的安全。這種加密需要能夠抵御密碼破譯者用他們自己的計算機進行的攻擊，因此現代加密方法依賴于這樣一種假設：哪些數學問題對計算機而言是難以解決的？

但在20世紀80年代，當密碼學家為這種信息安全方法奠定數學基礎時，一些研究人員發現，計算難度并不是守護秘密的唯一方法。量子理論起初是為了理解原子物理學而開發、構建，可事實證明，它竟然與信息和密碼學有著深刻的聯系。研究人員找到了一些方法，可以直接基于物理定律確保某些特定加密任務的安全性。但這些任務都屬于少見的特例——對于其他所有任務而言，除了經典計算方法之外，似乎別無他法。

到了20世紀末，量子密碼學研究人員認為這就是最后的答案了。但就在過去的幾年里，這個領域又發生了翻天覆地的變化。

“我們對量子密碼學可能實現的內容有了重新的認識。”美國哥倫比亞大學的量子信息理論家亨利·袁（Henry Yuen）說。

在最近的一系列論文中，研究人員表明，即使在幾乎所有計算都變得很容易的假想世界中，大多數加密任務仍然可以安全地完成。真正關鍵的是一個有關量子理論本身的特殊計算問題的難度。

“你所需要的假設可以非常、非常、非常弱，”位于美國加利福尼亞州伯克利的西蒙斯計算理論研究所的量子密碼學家費米·馬（Fermi Ma）表示，“這讓我們對計算難度本身有了新的認識。”

此信息將自動銷毀

故事開始于20世紀60年代末，當時一位名叫史蒂芬·威斯納（Stephen Wiesner）的物理學研究生開始思考量子理論中測量的破壞性。對任何受量子物理規則支配的系統進行測量，都會改變從數學層面描述其構形的量子狀態。對于大多數物理學家來說，這種量子測量干擾都是一種障礙。但威斯納持有以信息為中心的非正統觀點，他開始思考能否讓這種干擾變得有用。或許它可以成為敏感數據的一種內置防篡改保護。

但威斯納的想法過于超前，在研究生畢業后，他就離開了學術界。幸運的是，他曾與他的朋友、物理學家查爾斯·貝內特（Charles Bennett）討論過這些想法，后者在長達十年的時間里嘗試引起他人對此話題的興趣，始終未果。最后，1979年，貝內特在波多黎各的一次會議期間，于海邊游泳時遇到了計算機科學家吉爾斯·布拉薩德（Gilles Brassard）。他們合作撰寫了一篇開創性的論文，描述了一種解決重要加密任務的新方法。他們的協議基于量子測量干擾，無需任何關于計算問題難度的假設。

“量子信息在本質上似乎就是加密的。”費米·馬說。

貝內特和布拉薩德的突破讓研究人員變得樂觀起來，他們相信，其他加密任務也可以通過類似的量子技術達到完美的安全性。研究人員主要關注一種名為比特承諾的任務，它不僅本身非常有用，還是大多數高級加密協議的關鍵組成部分。

要理解比特承諾背后的基本概念，可以想象一場雙人游戲。在這場游戲中，你必須做出一個秘密決定，這個決定需要在稍后揭示。一種方法是把決定寫在紙條上，并放入密封的信封。這樣，你之后就無法更改決定，你的對手也無法偷看結果。

現在想象一下，你們在網上玩同樣的游戲。為了讓作弊成為不可能，你需要把決定封在一個數字信封里，讓雙方都無法單獨打開。這就是密碼學的用武之地。1981 年，計算機科學家先驅曼紐爾·布盧姆（Manuel Blum）構建了第一個比特承諾協議——一種利用難解的計算問題構造不可破解信封的方法。

但“難解”具體有多難？計算復雜性理論領域的研究人員研究了許多不同類型的難題，并非所有難題都對密碼學家有用。比特承諾和其他所有的加密協議都依賴于一類被復雜性理論學家稱為“NP”類的問題，這類問題的定義特征是很容易檢查候選解是否正確。

遺憾的是，研究人員尚未證明任何NP類問題都很難解。即使是看似最難的問題，也可能存在某種尚未發現的巧妙程序或算法能夠將其一舉解決。如果當真存在這樣的程序，那么整個經典密碼學都會崩潰。

這些考慮推動著人們探索基于量子的安全保證。但在1997年，兩篇論文證明，完全基于量子物理定律的比特承諾方案永遠不可能徹底安全。這兩篇論文暗示，幾乎所有加密任務都需要某種計算難度。

在接下來的近25年里，這成為量子比特承諾理論基礎的定論。然后，在2021年，一位名叫威廉·克雷其默（William Kretschmer）的研究生發表了一篇論文，促使研究人員面對一個從未有人想過的問題。對于比特承諾和大多數其他形式的密碼學來說，計算難度顯然是必要的，但究竟是哪一種難度呢？

答案比任何人預想的都要奇怪。

咨詢諭示

2021年的論文源于克雷其默想要努力理解一個概念上看似簡單的問題的特定版本：區分或判別兩種表面上相似的量子態到底有多難？克雷其默眼下是西蒙斯研究所的博士后研究員，而他最初對這個問題產生興趣的原因與比特承諾無關。

“密碼學根本不在我的考慮范圍內。”他說。

判別問題之所以有趣，部分原因在于，人們甚至不清楚如何用熟悉的數學語言來描述它。傳統上，復雜性理論學家研究的問題都有不同的可能輸入，這些輸入由位串（即0和1）表示。例如，對于將大數分解為質因數的任務，輸入的位串就代表要分解的數。

即使在研究人員開始研究如何利用量子物理進行計算之后，他們仍然把重點放在這種“經典輸入”問題上。典型的量子算法以普通的經典位串為起始，然后使用量子技巧對其進行處理。但在克雷其默研究的這類“量子輸入”問題中，輸入并非位串，而是容易被計算干擾的量子態（就和測量的干擾一樣）。

“我們無法使用傳統復雜性理論中用來描述量子計算的語言直接談論這些問題。”亨利·袁說。

起初，克雷其默認為他只需要把問題翻譯成更標準的語言，但他想不出該怎么做。于是，他做了復雜性理論學家在走投無路時經常做的事：求助于諭示。

在復雜性理論中，“諭示”（oracle）指的是一種可以即時解決特定問題的假想設備。能夠訪問諭示的計算機可能會通過咨詢諭示，將其作為算法的中間步驟，從而更輕松地解決其他問題。當然，諭示在現實世界中并不存在，但研究它們有助于復雜性理論學家理解不同問題的難度級別之間的關系。

克雷其默想知道，什么樣的諭示可以輕松區分兩種量子態，即所謂的態判別問題。他決定從一種特殊的諭示入手，這種諭示可以增強普通量子算法的能力，也就是那些利用量子技巧解決經典位串輸入問題的算法。這類算法可以解決某些對經典算法來說太難的問題，比如大數分解，但它們并非萬能的，還有許多問題超出了它們的能力范圍。

訪問克雷其默的諭示可以讓這些算法解決現實中的量子計算機難以解決的某些經典輸入問題。克雷其默本以為這些算法用來解決他的問題已經綽綽有余，但令他驚訝的是，他證明了這些加強版量子算法仍然被態判別問題難倒了。

“我完全被威廉的論文吸引了，”波士頓大學的密碼學研究生錢洛文（音譯）說，“我當時真的覺得它肯定錯了，因為它太反直覺了。”

錢洛文、亨利·袁等人很快證明，如果克雷其默的態判別問題真的很難解決，那么安全的量子比特承諾方案就可能實現。這反過來又意味著許多更高級的加密協議也擁有了安全性。量子加密的范圍遠比20世紀90年代的研究人員所意識到的要廣泛，而這一切都歸結于一個問題的難解程度。

能有多難？

克雷其默的結果有一個重大的前提——為了使證明成立，他不得不依賴一個只有量子算法才能咨詢的不尋常諭示。或許，一個更為熟悉的諭示會讓他的態判別問題變得更容易，從而使安全的量子比特承諾失效？2022年，克雷其默和錢洛文開始合作，研究他們能用一個人人都能理解的諭示證明出什么結論：一個可以瞬間解決任何NP問題的諭示。在擁有這種諭示的世界里，所有的經典加密都將失效。

克雷其默很快意識到，態判別問題在數學上與量子復雜性理論中一個看似不同的問題有著關聯，于是他請來了該領域的兩位專家——復雜性理論學家阿維謝·塔爾（Avishay Tal）和馬克蘭德·辛哈（Makrand Sinha）。“威廉就像個經理，而我們則是承包商。”塔爾說。

四位研究人員通力合作，很快就證明，即使是對于能夠調用這個NP諭示的計算機，克雷其默的態判別問題可能仍然是不可解的。這意味著，即使支撐起經典加密的每一個問題都變得容易，幾乎所有量子加密依然可以保持安全。經典密碼學和量子密碼學越來越像兩個完全獨立于彼此的世界。

這個結果引起了費米·馬的注意，他開始琢磨，自己能把克雷其默開創的研究方向推到多遠。即使引入更離奇的諭示——那些可以瞬間解決遠比NP難得多的計算問題的諭示——量子加密是否仍能保持安全呢？“NP類問題并不是經典問題中最難的，”美國伊利諾伊大學厄巴納-香檳分校的密碼學家達克希塔·庫拉納（Dakshita Khurana）表示，“還有比它們更難的。”

費米·馬與普林斯頓大學的密碼學家亞歷克斯·隆巴迪（Alex Lombardi）以及加州大學伯克利分校的量子計算研究員約翰·賴特（John Wright）集思廣益，思索如何以最佳方式解決這個問題。“這個問題真是太迷人、太令人費解了，”賴特說，“我立刻就被吸引住了。”

在思考了一段時間卻毫無進展后，費米·馬提出，他們應當考慮最極端的情況：一個可以瞬間解決任何經典輸入計算問題的諭示。這將囊括復雜性理論學家傳統上研究的一切問題，甚至包括那些在現實世界中被認為不可解的問題。

“我覺得這聽起來有點瘋。”隆巴迪說。

但是，這個問題卻取得了驚人的成果。經過近一年的努力，他們終于發表了一項驚人的結果。在能且只能咨詢一次全能諭示的情況下，沒有任何一個算法可以區分兩種量子態，做不到這點，就無法破壞量子比特承諾方案。

只允許算法單次查詢的限制并不像聽起來那么大，因為量子算法可以利用一種叫作疊加的現象，在實際上要求諭示同時解決多個問題。能夠連續進行多次查詢的算法可能會更強大，因為它們可以利用前次查詢的答案來決定下一次的查詢內容。這些算法是否也會受到類似的限制，仍然是一個懸而未決的問題。

費米·馬、隆巴迪和賴特的論文之所以意義重大，還有另一個原因。在這三位研究人員研究他們的問題時，他們意識到它與復雜性理論學家斯科特 · 阿倫森（Scott Aaronson）和數學家格雷格·庫珀伯格（Greg Kuperberg）在16年前提出的一個重大未解問題密切相關，該問題涉及將一種量子態轉化為另一種量子態的難度。這篇新論文是解決該問題的第一個重大進展。

“這是一個非常強有力的結果，也是一個非常令人驚訝的結果。”京都湯川理論物理研究所的量子密碼學研究員森前智行表示。

一系列的最新成果表明，區分兩種量子態這個看似無害的問題不僅很難，而且幾乎是難以想象的難——遠遠超出了普通甚至更離奇的量子算法的能力范圍。這對密碼學來說是好消息，但對以量子態為輸入的計算問題也有更廣泛的影響。傳統的復雜性理論似乎無法解決這些問題。要真正理解這些問題，可能需要一個全新的理論框架。

“感覺量子信息的行為方式有一些根本性的不同，”美國華盛頓大學的量子密碼學家安德烈亞·克拉丹杰洛（Andrea Coladangelo）說，“它一定還與密碼學之外的領域存在聯系。”

資料來源 Quanta Magazine