在計(jì)算機(jī)領(lǐng)域，解決格上的近似最短向量問(wèn)題（Approximate Shortest Vector Problems in Lattices。Lattice Problems）以及與之等價(jià)的容錯(cuò)學(xué)習(xí)問(wèn)題（Learning with Errors，LWE）是經(jīng)典的算法難題，科學(xué)界普遍認(rèn)為它們超出了傳統(tǒng)計(jì)算機(jī)的能力范圍。

量子計(jì)算機(jī)是否有望能破解 Lattice Problems 以及 LWE？雖然這一問(wèn)題長(zhǎng)期以來(lái)受到關(guān)注，但鮮有實(shí)質(zhì)性進(jìn)展。

近日，清華大學(xué)交叉信息研究院助理教授陳一鐳在 eprint 上發(fā)布的一篇論文，給出了破解格密碼的量子算法，引發(fā)了全球計(jì)算機(jī)領(lǐng)域的震撼。

• 論文地址：https://eprint.iacr.org/2024/555.pdf
• 論文標(biāo)題：Quantum Algorithms for Lattice Problems

清華大學(xué)在今天的官方公告中表示：「陳一鐳的工作提出了一個(gè)全新的量子算法來(lái)解決 LWE 以及與之等價(jià)的格問(wèn)題。這項(xiàng)工作仍在同行評(píng)議中。如果被驗(yàn)證為正確，將為這個(gè)懸而未決的問(wèn)題給出肯定的答復(fù)。」

它在科學(xué)上的意義將是雙層的：第一，這將是自 30 年前 Peter Shor 提出大數(shù)分解的量子算法以來(lái)，最重要的量子算法突破。

第二，這將對(duì)美國(guó) NIST 過(guò)去 10 年來(lái)選擇后量子密碼設(shè)計(jì)的思路產(chǎn)生顛覆性的影響，因?yàn)槎鄶?shù)選出的后量子密碼方案都是基于 Lattice Problems 或 LWE。陳一鐳的工作無(wú)疑將使他們安全性受到質(zhì)疑。

這篇論文提出的算法及分析極為新穎而深?yuàn)W?；叵?Wiles 1994 年解決費(fèi)馬大定理（Fermat's Last Theorem），以及 Perelman 2002 年解決龐佳萊猜想（Poincaré Conjecture）后，都經(jīng)過(guò)一年以上專家們方能徹底認(rèn)證其正確性。陳一鐳的工作，預(yù)料也需要數(shù)月時(shí)間才能完成驗(yàn)證認(rèn)可。我們靜候科學(xué)界對(duì)此工作的后續(xù)反應(yīng)。

對(duì)此，圖靈獎(jiǎng)得主、量子計(jì)算領(lǐng)域權(quán)威、清華交叉信息研究院院長(zhǎng)姚期智給出高度評(píng)價(jià)：「作為一個(gè)青年教師，陳一鐳能勇于挑戰(zhàn)如格密碼這樣的世界級(jí)科學(xué)難題，令人贊佩！」

從論文致謝部分的內(nèi)容來(lái)看，為理論計(jì)算機(jī)領(lǐng)域引入格密碼和容錯(cuò)學(xué)習(xí)問(wèn)題的紐約大學(xué)計(jì)算機(jī)科學(xué)家、2018 年哥德爾獎(jiǎng)得主 Oded Regev 本人應(yīng)該已經(jīng)看過(guò)論文手稿。

那么，這篇論文究竟取得了怎樣的突破？

具體而言，這篇論文展示了一種多項(xiàng)式時(shí)間量子算法，用于求解具有特定多項(xiàng)式模數(shù) - 噪聲比的有誤學(xué)習(xí)問(wèn)題（LWE）。結(jié)合 Regev [J.ACM 2009] 所展示的從格問(wèn)題到 LWE 的還原，論文得到了多項(xiàng)式時(shí)間量子算法，用于求解所有 n 維網(wǎng)格的決定性最短向量問(wèn)題（GapSVP）和最短獨(dú)立向量問(wèn)題（SIVP），其近似因子為。在此之前，還沒(méi)有任何多項(xiàng)式甚至亞指數(shù)時(shí)間的量子算法可以在任何多項(xiàng)式近似因子內(nèi)求解所有格的 GapSVP 或 SIVP。

為了開發(fā)求解 LWE 的量子算法，這篇論文主要引入了兩種新技術(shù)：

首先，陳一鐳在量子算法的設(shè)計(jì)中引入了具有復(fù)雜方差的高斯函數(shù)，特別是利用了復(fù)高斯函數(shù)離散傅里葉變換中的卡斯特波特征。其次，陳一鐳使用帶有復(fù)高斯窗口的窗口量子傅里葉變換，這使得能夠結(jié)合時(shí)域和頻域的信息。利用這些技術(shù)，陳一鐳將 LWE 實(shí)例轉(zhuǎn)換為具有純虛高斯振幅的量子態(tài)，然后將純虛高斯態(tài)轉(zhuǎn)換為 LWE 秘密和誤差項(xiàng)的經(jīng)典線性方程，最后利用高斯消元法求解線性方程組。

求解 LWE 的量子算法

論文第三章主要專注于定理的證明：

• 3.1 節(jié)展示了具有幾個(gè)已知秘密坐標(biāo)的 LWE 和標(biāo)準(zhǔn) LWE 一樣難；
• 3.2 介紹了將 LWE 轉(zhuǎn)換成具有唯一最短向量的特殊 q-ary 格；
• 3.3 節(jié)列出了主要量子算法中使用的參數(shù)；
• 3.4 節(jié)概述了主要的量子算法；
• 3.5 節(jié)詳細(xì)提供了主要量子算法的九個(gè)步驟，但將所有長(zhǎng)度超過(guò)三頁(yè)的證明推遲到第 3.6 節(jié)；
• 3.6 節(jié)提供了第 3.5 節(jié)中遺漏的所有詳細(xì)證明。

具體而言：

論文展示了 LWE 的三種變體，最后一個(gè)變體在 Def. 3.4 中正式定義，本文提出的量子算法最終將解決這個(gè)問(wèn)題。 

下面三種縮減都是對(duì)現(xiàn)有經(jīng)典多項(xiàng)式時(shí)間縮減的微小修改，從標(biāo)準(zhǔn) LWE 到它們的變體。

1. 有 k 個(gè)無(wú)誤差坐標(biāo)的 LWE。

2. 有 k 個(gè)選擇誤差項(xiàng)的 LWE。

3.LWE，秘密遵循誤差分布。

將 LWE 轉(zhuǎn)換成具有唯一最短向量的特殊 q-ary 格

現(xiàn)在定義一個(gè) q-ary 格，使得找到這個(gè)特殊 q-ary 格的唯一最短向量意味著求解。設(shè)：

參數(shù)選擇

本小節(jié)將介紹更多量子算法中使用的參數(shù)。設(shè) D ∈ N + 為縮放參數(shù)。

參數(shù)是在以下約束下設(shè)置的（ ）：

量子算法有九個(gè)步驟，下面的每個(gè)條件通常只在一個(gè)或幾個(gè)步驟中使用：

主要量子算法的詳細(xì)概述

本節(jié)中，作者運(yùn)行一個(gè)由 9 大步驟組成的量子子程序，時(shí)間復(fù)雜度為 O (n) 次。每次運(yùn)行量子子程序時(shí)都會(huì)獲得一個(gè)經(jīng)典線性方程，其中隨機(jī)系數(shù)在中的最短向量上（與 LWE 秘密和誤差向量相關(guān)）。因此，運(yùn)行 O (n) 次后將得到一個(gè)滿秩線性方程組，并通過(guò)高斯消元法計(jì)算 LWE 秘密項(xiàng)和誤差項(xiàng)。

如下為量子子程序中 9 大步驟的高級(jí)描述，包括了每個(gè)步驟中獲得的狀態(tài)以及經(jīng)典信息。 

主要量子子程序：9 大步驟詳解

步驟 1：在上準(zhǔn)備一個(gè)疊加，并應(yīng)用復(fù)高斯窗。

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

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

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

步驟 5：將 |φ_4? 劃分為了高階和低階 |h′? |h′′?，然后測(cè)量 |h′′?。為了推導(dǎo)出 |φ_5?的表達(dá)式，作者注意到 |φ_4? 可以等效地寫為：

步驟 6：在 |φ_5?應(yīng)用。

步驟 7：提取 |φ_6? 的中心，得到純虛高斯態(tài) |φ_7?。

步驟 8：提取 v′_1 mod D^2_p1 并保留 |φ_8? = |φ_7?。

在第 8 步中，作者首先執(zhí)行四次操作，然后進(jìn)行部分測(cè)量，最后將這四次操作反轉(zhuǎn)（將確保這四次操作是可逆的）。目標(biāo)是提取 v′_1 mod D^2_p1，最終返回到 |φ_7?。也就是說(shuō)，將學(xué)習(xí) v′_1 mod D^2_p1 而不折疊或修改 |φ_7?。

步驟 9：從 v′_1 mod D^2_p1 和 |φ_8? 中提取秘密上的線性方程。

在第 9 步中，作者的目標(biāo)是將 |φ_8? 轉(zhuǎn)換為秘密上的經(jīng)典線性方程，最終給出如下主引理（引理 3.8）的證明。步驟 9 使用步驟 8 中獲得的 v′_1 mod D^2_p1 信息，并插入 LWE 秘密中的已知項(xiàng)的 κ-1 坐標(biāo)。

陳一鐳簡(jiǎn)介

陳一鐳是清華大學(xué)交叉信息學(xué)院助理教授，上海期智研究院 PI。曾任 VISA 研究院研究員。于 2018 年獲得波士頓大學(xué)計(jì)算機(jī)博士學(xué)位，本科畢業(yè)于上海交通大學(xué)。主要研究興趣是密碼學(xué)，特別是在偽隨機(jī)，格密碼，數(shù)論，和量子計(jì)算等方向。

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

也就是說(shuō)，在 2022 年，陳一鐳就發(fā)表了有關(guān)格問(wèn)題的研究。該研究「Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering」發(fā)表于 2022 年歐洲密碼大會(huì)（Eurocrypt 2022），并收到 Journal of Cryptology 邀稿。

在 2022 年這篇研究中，陳一鐳團(tuán)隊(duì)和普林斯頓大學(xué)的劉啟鵬和 Mark Zhandry 提出了一個(gè)能解決特殊格問(wèn)題的多項(xiàng)式時(shí)間量子算法。這些特殊格問(wèn)題是 SIS 和 LWE 的變種。他們雖然并不等價(jià)于標(biāo)準(zhǔn)的格問(wèn)題，但是已經(jīng)非常接近于密碼學(xué)常用的問(wèn)題。他們的量子算法中使用了一種被稱為 “過(guò)濾” 的方法，是在量子算法的設(shè)計(jì)中第一次使用，可能為未來(lái)量子算法的設(shè)計(jì)帶來(lái)新的思路。