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

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

到了20世紀(jì)末，量子密碼學(xué)研究人員認(rèn)為這就是最后的答案了。但就在過去的幾年里，這個領(lǐng)域又發(fā)生了翻天覆地的變化。

“我們對量子密碼學(xué)可能實現(xiàn)的內(nèi)容有了重新的認(rèn)識?！泵绹鐐惐葋喆髮W(xué)的量子信息理論家亨利·袁（Henry Yuen）說。

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

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

此信息將自動銷毀

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

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

“量子信息在本質(zhì)上似乎就是加密的?！辟M米·馬說。

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

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

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

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

遺憾的是，研究人員尚未證明任何NP類問題都很難解。即使是看似最難的問題，也可能存在某種尚未發(fā)現(xiàn)的巧妙程序或算法能夠?qū)⑵湟慌e解決。如果當(dāng)真存在這樣的程序，那么整個經(jīng)典密碼學(xué)都會崩潰。

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

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

答案比任何人預(yù)想的都要奇怪。

咨詢諭示

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

“密碼學(xué)根本不在我的考慮范圍內(nèi)?！彼f。

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

即使在研究人員開始研究如何利用量子物理進行計算之后，他們?nèi)匀话阎攸c放在這種“經(jīng)典輸入”問題上。典型的量子算法以普通的經(jīng)典位串為起始，然后使用量子技巧對其進行處理。但在克雷其默研究的這類“量子輸入”問題中，輸入并非位串，而是容易被計算干擾的量子態(tài)（就和測量的干擾一樣）。

“我們無法使用傳統(tǒng)復(fù)雜性理論中用來描述量子計算的語言直接談?wù)撨@些問題?！焙嗬ぴf。

起初，克雷其默認(rèn)為他只需要把問題翻譯成更標(biāo)準(zhǔn)的語言，但他想不出該怎么做。于是，他做了復(fù)雜性理論學(xué)家在走投無路時經(jīng)常做的事：求助于諭示。

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

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

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

“我完全被威廉的論文吸引了，”波士頓大學(xué)的密碼學(xué)研究生錢洛文（音譯）說，“我當(dāng)時真的覺得它肯定錯了，因為它太反直覺了?！?/p>

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

能有多難？

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

克雷其默很快意識到，態(tài)判別問題在數(shù)學(xué)上與量子復(fù)雜性理論中一個看似不同的問題有著關(guān)聯(lián)，于是他請來了該領(lǐng)域的兩位專家——復(fù)雜性理論學(xué)家阿維謝·塔爾（Avishay Tal）和馬克蘭德·辛哈（Makrand Sinha）?！巴拖駛€經(jīng)理，而我們則是承包商?！彼栒f。

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

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

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

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

“我覺得這聽起來有點瘋?！甭“偷险f。

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

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

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

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

一系列的最新成果表明，區(qū)分兩種量子態(tài)這個看似無害的問題不僅很難，而且?guī)缀跏请y以想象的難——遠(yuǎn)遠(yuǎn)超出了普通甚至更離奇的量子算法的能力范圍。這對密碼學(xué)來說是好消息，但對以量子態(tài)為輸入的計算問題也有更廣泛的影響。傳統(tǒng)的復(fù)雜性理論似乎無法解決這些問題。要真正理解這些問題，可能需要一個全新的理論框架。

“感覺量子信息的行為方式有一些根本性的不同，”美國華盛頓大學(xué)的量子密碼學(xué)家安德烈亞·克拉丹杰洛（Andrea Coladangelo）說，“它一定還與密碼學(xué)之外的領(lǐng)域存在聯(lián)系?！?/p>

資料來源 Quanta Magazine