一直以來，解決格上的近似最短向量問題（Lattice Problems）以及帶錯誤學(xué)習(xí)問題（LWE），都是計算機領(lǐng)域的經(jīng)典算法難題。

尤其是在科學(xué)界看來，它們遠遠超出了傳統(tǒng)計算機的能力范圍。

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

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

預(yù)印本論文一經(jīng)發(fā)表，便在整個計算機界引起了巨大的轟動。

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

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

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

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

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

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

為了開發(fā)求解LWE的量子算法，作者提出了兩種新的技術(shù)：

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

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

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

但遺憾的是，Hongxun Wu（UC伯克利博二學(xué)生）和Thomas Vidick（量子領(lǐng)域?qū)＜遥┌l(fā)現(xiàn)，算法的第9步實際上存在一個尚不能修復(fù)的bug。

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

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

九大關(guān)鍵步驟

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

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

其中，每次調(diào)用都會得到一個經(jīng)典線性方程，其隨機系數(shù)是中最短的向量（與LWE秘密向量和錯誤向量相關(guān)）。

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

步驟 1：在上進行疊加，并應(yīng)用復(fù)高斯窗口

步驟 2：在|φ1?上應(yīng)用

步驟 3：在|φ2?上應(yīng)用復(fù)高斯窗口，得到|φ3?和z′

步驟 4：在|φ3?上應(yīng)用

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

步驟 6：在|φ5?上應(yīng)用

步驟 7：提取|φ6?的中心，得到純虛高斯?fàn)顟B(tài)|φ7?

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

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

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

第9步的目標(biāo)是將|φ8?轉(zhuǎn)換為秘密的經(jīng)典線性方程，并最終得到主Lemma（3.8）的證明。

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

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

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

作者介紹

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

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

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

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