解決難題的最佳方法是什麼？這是計算機科學子領域「計算複雜性理論」的核心問題。這是一個很難回答的問題，但是翻轉一下，就會變得更容易。最糟糕的方法幾乎總是反覆試驗，其中包括插入可能的解決方案，直到找到可行的解決方案。但對於某些問題，似乎根本沒有其他選擇──最糟糕的方法也是最好的方法。

研究人員長期以來一直想知道情況是否真的如此，說 拉胡爾·伊蘭戈，麻省理工學院研究複雜性理論的研究生。 “你可能會問，’是否存在猜測和檢查最適合解決的問題？’”

複雜性理論學家研究了許多計算問題，即使是困難的問題也常常承認某種巧妙的程式或演算法，這使得找到解決方案比純粹的試誤更容易一些。少數例外是所謂的壓縮問題，其目標是找到資料集的最短描述。

但去年 11 月，兩組研究人員 獨立地 發現 另一種用於壓縮問題的演算法——比檢查所有可能的答案稍快。新方法的工作原理是採用密碼學家 25 年前發明的演算法來解決不同的問題。只有一個限制：您需要根據資料集的大小自訂演算法。

「它們確實是美麗且重要的結果，」說 埃里克·阿倫德，羅格斯大學理論計算機科學家。

定義硬度

這些新結果是對一個問題的最新研究，這個問題最早是在蘇聯研究的，早在複雜性理論出現之前。 「在我上小學之前，俄羅斯人就已經制定了這個，」阿倫德說。

這些蘇聯研究人員研究的具體計算問題稱為最小電路尺寸問題，類似於電腦硬體設計者一直面臨的問題。如果您獲得了電子電路應如何工作的完整規範，您能找到能夠完成這項工作的最簡單的電路嗎？沒有人知道如何在沒有「perebor」（俄語單字大致相當於「窮舉搜尋」）的情況下解決這個問題。

最小電路尺寸問題是壓縮問題的一個例子。您可以使用一長串位元（0 和 1）來描述電路的行為，然後詢問是否有一種方法可以使用更少的位元來重現相同的行為。檢查所有可能的電路佈局所需的時間會隨著字串中位數的增加而呈指數增長。

這種指數成長是硬計算問題的定義特徵。但並非所有難題都同樣困難——有些問題的演算法比窮舉搜尋更快，儘管它們的運行時間仍然呈指數級增長。用現代術語來說，最重要的問題是是否存在針對壓縮問題的此類演算法。

1959 年，一位名叫 Sergey Yablonsky 的著名研究人員聲稱已經證明窮舉搜尋確實是解決最小電路尺寸問題的唯一方法。但他的證明留下了一些漏洞。當時一些研究人員注意到了這些缺陷，但亞布隆斯基的影響力足以阻止大多數其他人研究佩雷博爾問題。

在接下來的幾十年裡，很少有研究人員研究壓縮問題，而 Perebor 問題主要被認為是複雜性理論史前史的一個腳註。最近，在研究人員發現壓縮問題與密碼學基礎之間存在奇怪的關聯之後，這個問題才得到了廣泛的關注。

單向行駛

現代密碼學使用困難的計算問題來保護秘密訊息。但計算難度只有在不對稱的情況下才有用——如果很難破解編碼訊息，但首先編碼訊息並不困難。

在每個加密方案中，這種不對稱性的根源是一種稱為單向函數的數學對象，它將輸入位元串轉換為相同長度的輸出串。給定單向函數的輸入，很容易計算輸出，但給定輸出很難反轉函數 - 即對其進行逆向工程並恢復輸入。

「密碼學家真的希望擁有非常非常高效的可計算單向函數，而且這些函數真的非常難以逆，」阿倫德說。許多數學函數似乎都具有這種性質，而求逆這些函數的困難源自於解決不同計算問題的明顯困難。

不幸的是，密碼學家不確定這些函數中的任何一個是否真的很難反轉——事實上，真正的單向函數可能不存在。這種不確定性仍然存在，因為複雜性理論家已經 奮鬥了50年 證明看似困難的問題確實很難。如果不是這樣，並且如果研究人員發現了解決這些問題的超快演算法，這對密碼學來說將是災難性的——就像突然在單向街道上為兩個方向超速行駛的汽車分配路線一樣。

儘管對計算難度的全面理解仍然難以捉摸，但密碼學家最近在單向函數的統一理論方面取得了令人興奮的進展。 2020 年，特拉維夫大學密碼學家邁出了一大步 拉斐爾山口 和他的研究生 劉彥一 證明單向函數是 密切相關 一個特定的壓縮問題，稱為有時間限制的柯爾莫哥洛夫複雜度問題。

如果這個問題對大多數輸入來說確實很難解決，那麼Pass 和Liu 的結果就提供了一種如何建立可證明困難的單向函數的方法——即使其他計算問題變得容易得多，也可以保證該函數的安全性超出研究人員的預期。但如果有一個快速演算法可以解決有時間限制的柯爾莫哥洛夫複雜性問題，那麼密碼學就注定失敗，任何函數都可以輕鬆反轉。基於這個問題的難度的單向函數是可能的最安全的函數——一種統治所有問題的單向函數。

基於資料結構

Pass 和 Liu 的發現是一系列研究的最新篇章，這些研究利用複雜性理論來更好地理解密碼學的基礎。但它也提出了一種反轉這種關係的方法：有時間限制的柯爾莫哥洛夫複雜性問題和函數反轉之間的等價性意味著對任一問題的見解可以揭示更多關於另一個問題的資訊。幾十年來，密碼學家一直在研究函數求逆演算法，以便更好地理解其加密方法的弱點。研究人員開始想知道這些演算法是否可以幫助回答複雜性理論中古老的問題。

與許多計算問題一樣，函數反演可以透過窮舉搜尋來解決。給定一個輸出字串，只需將所有可能的輸入插入函數中，直到找到能產生正確答案的輸入。

1980 年，密碼學家 Martin Hellman 開始研究是否可以做得更好——這與幾十年前蘇聯數學家就壓縮問題提出的問題是一樣的。海爾曼 發現 是的，這是可能的——只要您願意提前投入一些額外的工作，使用稱為資料結構的數學物件。

資料結構本質上是一張表，儲存有關要反轉的函數的信息，建構資料結構需要針對某些策略選擇的輸入計算函數的輸出。所有這些計算“可能需要很長時間”，他說 瑞安·威廉姆斯，麻省理工學院的複雜性理論家。 “但我們的想法是，這是一次、一勞永逸的。”如果您嘗試在給定許多不同輸出的情況下反轉同一函數（例如，解碼以相同方式加密的許多不同訊息），那麼提前完成這項工作可能是值得的。

當然，儲存額外的資訊需要空間，因此將這種策略發揮到極致，您最終可能會得到一個無法安裝在任何電腦上的快速程式。 Hellman 設計了一個巧妙的資料結構，讓他的演算法比窮舉搜尋稍微快一點地反轉大多數函數，而不會佔用太多空間。然後在 2000 年，密碼學家 Amos Fiat 和 Moni Naor 擴展 Hellman 對所有函數的論證。

2020 年帕斯和劉的突破之後，這些舊的結果突然變得新的相關性。 Fiat-Naor 演算法可以比窮舉搜尋更快地反轉任意函數。它也可以解決壓縮問題嗎？

不穿制服

第一個提出這個問題的研究者是複雜性理論家 拉胡爾桑塔南 牛津大學教授和他的研究生 任翰林。他們這樣做是在 2021紙 證明壓縮問題和函數反演的相互關係比研究人員意識到的更緊密。

Pass和Liu證明，如果有時間限制的Kolmogorov複雜性問題是困難的，那麼函數反演也一定是困難的，反之亦然。但問題可能很困難，但仍然需要比窮舉搜尋更好的解決方案。 Santhanam 和 Ren 表明，一個問題是否需要窮舉搜尋與另一個問題是否需要窮舉搜尋之間有密切的關聯。

他們的結果對研究人員經常研究的兩大類演算法（稱為「均勻」和「非均勻」演算法）有不同的影響。統一演算法對每個輸入都遵循相同的過程——例如，用於對數字列表進行排序的統一程序，無論列表中有 20 個條目還是 20,000 個條目，都將以相同的方式工作。相反，非均勻演算法對不同長度的輸入使用不同的過程。

Fiat-Naor 演算法使用的資料結構始終針對特定功能進行客製化。要反轉擾亂 10 位元字串的函數，您需要一個與反轉擾亂 20 位元字串的函數所需的資料結構不同的資料結構，即使擾亂是以類似的方式完成的。這使得 Fiat-Naor 成為一種非均勻演算法。

Santhanam 和 Ren 的結果表明，有可能將 Fiat-Naor 演算法轉變為解決壓縮問題的演算法。但將演算法從一個問題應用到另一個問題並不簡單，他們也沒有進一步研究這個問題。

一年後，帕斯在慶祝 Naor 對密碼學貢獻的研討會上聽到 Fiat 關於經典演算法的演講後，偶然發現了同樣的想法。 「從那時起，使用函數反轉的想法就一直在我的腦海中，」他說。後來他開始與特拉維夫大學的研究人員認真研究這個問題 諾姆·馬佐爾.

同時，在訪問加州柏克萊西蒙斯計算理論研究所時，Ilango 在與包括 Santhanam 在內的其他研究人員討論後，受到啟發，開始解決這個問題。 「這是一次非常偶然的談話，你只是在亂扔東西，」桑塔南說。伊蘭戈後來與威廉斯聯手， 平原修一，東京國家資訊研究所的複雜性理論家。

困難的部分是弄清楚如何將 Fiat-Naor 演算法核心的資料結構嵌入到解決壓縮問題的非均勻演算法中。有一個執行這種嵌入的標準程序，但它會減慢演算法速度，消除其相對於窮舉搜尋的優勢。兩個團隊找到了更聰明的方法來合併 Fiat-Naor 資料結構，並獲得了適用於所有輸入且比窮舉搜尋更快的壓縮問題演算法。

兩種演算法的細節略有不同。即使將搜尋限制為最簡單的可能性，Ilango 和他的合著者提出的方法也比窮舉搜尋更快，並且它適用於所有壓縮問題- 受時間限制的Kolmogorov 複雜性、最小電路尺寸問題以及許多其他問題。但兩種演算法的核心思想是相同的。密碼學技術已經證明了它們在這個新領域的價值。

反演收斂

非均勻演算法的新證明提出了一個自然的問題：均勻演算法怎麼樣？有沒有一種方法可以比使用它們進行窮舉搜尋更快地解決壓縮問題？

最近的一系列結果表明，任何此類演算法都相當於用於反轉任意函數的統一演算法——這是密碼學家幾十年來一直在尋求的結果。正因為如此，許多研究人員發現這種可能性不大。

「我會非常驚訝，」桑塔南說。 “這需要一個全新的想法。”

但阿倫德表示，研究人員不應忽視這種可能性。 「對我來說，一個很好的工作假設是，如果有一種非統一的方式來做某事，那麼很可能存在一種統一的方式，」他說。

不管怎樣，這項工作讓複雜性理論家對密碼學中的老問題重新產生了興趣。 尤瓦爾·伊沙伊（Yuval Ishai）以色列海法理工學院的密碼學家表示，這才是最令人興奮的地方。

「我真的很高興看到不同社區之間的利益趨同，」他說。 “我認為這對科學很有好處。”