前段時間，由清華大學(xué)交叉信息研究院助理教授陳一鐳提出的全新「破解格密碼的量子算法」，一經(jīng)發(fā)表便引發(fā)了業(yè)內(nèi)轟動。然而就在最近，關(guān)鍵的第 9 步被發(fā)現(xiàn)有無法修復(fù)的 bug，導(dǎo)致算法無法成立。
一直以來，解決格上的近似最短向量問題（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ā)了篇博客文章，詳細討論了論文所帶來的影響。
具體來說，陳教授提出的這種多項式時間量子算法，主要用于求解具有特定多項式模數(shù)-噪聲比的「帶錯誤學(xué)習(xí)問題」（LWE）。
通過結(jié)合 Regev 所提出的從網(wǎng)格問題到 LWE 的還原，便可以獲得多項式時間量子算法，并可以在
的近似因子內(nèi)求解所有 n 維網(wǎng)格的決策最短向量問題（GapSVP）和最短獨立向量問題（SIVP）。
在此之前，還沒有已知的多項式甚至亞指數(shù)時間量子算法可以在任何多項式近似因子內(nèi)求解所有網(wǎng)格的 GapSVP 或 SIVP。
為了開發(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 問題或許會將有別的解決方法。
9 大關(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?的中心，得到純虛高斯狀態(tài) |φ7?
步驟 8：提取并保留 |φ8?=|φ7?
在步驟 8 中，作者首先進行四次運算（可逆），然后進行部分測量，最后將四次運算反轉(zhuǎn)。也就是說，需要在不折疊或修改 |φ7?的情況下，學(xué)習(xí)
。
步驟 9：從和 |φ8?中提取秘密的線性方程
第 9 步的目標是將 |φ8?轉(zhuǎn)換為秘密的經(jīng)典線性方程，并最終得到主 Lemma（3.8）的證明。
其中，步驟 9 使用步驟 8 中獲得的
信息，以及插入 LWE 秘密中的已知項的 κ-1 坐標。
這里，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)造。
參考資料：
https://www.zhihu.com/question/652567682
https://sqz.ac.cn/password-50
http://www.chenyilei.net/
https://eprint.iacr.org/2024/555
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。