一直以來，解決格上的近似最短向量問題（Lattice Problems）以及帶錯誤學習問題（LWE），都是計算機領域的經典算法難題。

尤其是在科學界看來，它們遠遠超出了傳統計算機的能力范圍。

那么，量子計算機有望能破解Lattice Problems以及LWE嗎？

前段時間，來自清華大學交叉信息研究院陳一鐳助理教授，便針對這些問題提出了一種全新的「破解格密碼的量子算法」。

預印本論文一經發表，便在整個計算機界引起了巨大的轟動。

如著名密碼學家N. P. Smart，就在第一時間發了篇博客文章，詳細討論了論文所帶來的影響。

文章地址：https://nigelsmart.github.io/LWE.html

具體來說，陳教授提出的這種多項式時間量子算法，主要用于求解具有特定多項式模數-噪聲比的「帶錯誤學習問題」（LWE）。

通過結合Regev所提出的從網格問題到LWE的還原，便可以獲得多項式時間量子算法，并可以在的近似因子內求解所有n維網格的決策最短向量問題（GapSVP）和最短獨立向量問題（SIVP）。

在此之前，還沒有已知的多項式甚至亞指數時間量子算法可以在任何多項式近似因子內求解所有網格的GapSVP 或SIVP。

論文地址：https://eprint.iacr.org/2024/555.pdf

為了開發求解LWE的量子算法，作者提出了兩種新的技術：

首先，在量子算法的設計中引入具有復雜方差的高斯函數。特別是，利用復高斯函數離散傅里葉變換中的卡斯特波特征。

其次，使用帶有復高斯窗口的窗口量子傅里葉變換，從而能夠結合時域和頻域的信息。

基于此，便可以先將LWE實例轉換為具有純虛高斯振幅的量子態，然后將純虛高斯態轉換為LWE秘密和誤差項的經典線性方程，最后利用高斯消元法求解線性方程組。

但遺憾的是，Hongxun Wu（UC伯克利博二學生）和Thomas Vidick（量子領域專家）發現，算法的第9步實際上存在一個尚不能修復的bug。

也就是說，這個通過多項式模數-噪聲比，來求解LWE的多項式時間量子算法，無法成立了。

對此作者表示，希望像復高斯（Complex Gaussian）和窗口QFT（windowed QFT）這樣的想法，會在量子計算中找到其他應用，而LWE問題或許會將有別的解決方法。

九大關鍵步驟

首先進行參數的設置，之后需要運行一個由九個步驟組成的量子子程序，共運行O(n)次。

論文中最關鍵的，是一個需要調用O(n)次的，由九個步驟組成的量子子程序。

其中，每次調用都會得到一個經典線性方程，其隨機系數是中最短的向量（與LWE秘密向量和錯誤向量相關）。

在調用完O(n)次之后，便可以得到一個全秩線性方程組，并通過高斯消元法計算出LWE秘密和錯誤項。

步驟 1：在上進行疊加，并應用復高斯窗口

步驟 2：在|φ1?上應用

步驟 3：在|φ2?上應用復高斯窗口，得到|φ3?和z′

步驟 4：在|φ3?上應用

步驟 5：將|φ4?分割成高階|h′?和低階|h′′?，然后對|h′′?進行測量

步驟 6：在|φ5?上應用

步驟 7：提取|φ6?的中心，得到純虛高斯狀態|φ7?

步驟 8：提取并保留|φ8?=|φ7?

在步驟8中，作者首先進行四次運算（可逆），然后進行部分測量，最后將四次運算反轉。也就是說，需要在不折疊或修改|φ7?的情況下，學習。

步驟 9：從和|φ8?中提取秘密的線性方程

第9步的目標是將|φ8?轉換為秘密的經典線性方程，并最終得到主Lemma（3.8）的證明。

其中，步驟9使用步驟8中獲得的信息，以及插入LWE秘密中的已知項的κ-1坐標。

這里，bug來了：|φ8.f?的振幅不滿足M2周期性。

或者，另一種解釋是：|φ8.f?包含p1...pκ向量。經過域擴展后，本應得到p1p2...pκ-p2...pκ向量，但按照|φ8.g?的寫法，它只包含p1...pκ向量。因此|φ8.g?的表達式是錯誤的。

作者介紹

陳一鐳是清華大學交叉信息學院（IIIS）的一名助理教授。

此前，他在波士頓大學獲得博士學位，指導老師是Ran Canetti教授和Leonid Reyzin教授。并在上海交通大學獲得學士學位。在那里，一個有趣的問題引導他走上了科研之路。

他的研究興趣是密碼學，特別是在偽隨機，格密碼，數論，和量子計算等方向。

主要成果有：設計了格問題的量子算法，建立了多線性映射和代碼混淆在格問題上安全實現的基礎，提出了證明Fiat-Shamir假設的方法，以及提出了一個不可逆群的構造。