☰

若通過驗證可顛覆美國後量子密碼設計，清華陳一鐳論文破解格密碼

機器之心報道

機器之心編輯部

在計算機領域，解決格上的近似最短向量問題（Approximate Shortest Vector Problems in Lattices。Lattice Problems）以及與之等價的容錯學習問題（Learning with Errors，LWE）是經典的算法難題，科學界普遍認爲它們超出了傳統計算機的能力範圍。

量子計算機是否有望能破解 Lattice Problems 以及 LWE？雖然這一問題長期以來受到關注，但鮮有實質性進展。

近日，清華大學交叉信息研究院助理教授陳一鐳在 eprint 上發佈的一篇論文，給出了破解格密碼的量子算法，引發了全球計算機領域的震撼。

清華大學在今天的官方公告中表示：「陳一鐳的工作提出了一個全新的量子算法來解決 LWE 以及與之等價的格問題。這項工作仍在同行評議中。如果被驗證爲正確，將爲這個懸而未決的問題給出肯定的答覆。」

對此，圖靈獎得主、量子計算領域權威、清華交叉信息研究院院長姚期智給出高度評價：「作爲一個青年教師，陳一鐳能勇於挑戰如格密碼這樣的世界級科學難題，令人讚佩！」

從論文致謝部分的內容來看，爲理論計算機領域引入格密碼和容錯學習問題的紐約大學計算機科學家、2018 年哥德爾獎得主 Oded Regev 本人應該已經看過論文手稿。

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

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

爲了開發求解 LWE 的量子算法，這篇論文主要引入了兩種新技術：

首先，陳一鐳在量子算法的設計中引入了具有複雜方差的高斯函數，特別是利用了復高斯函數離散傅里葉變換中的卡斯特波特徵。其次，陳一鐳使用帶有復高斯窗口的窗口量子傅里葉變換，這使得能夠結合時域和頻域的信息。利用這些技術，陳一鐳將 LWE 實例轉換爲具有純虛高斯振幅的量子態，然後將純虛高斯態轉換爲 LWE 秘密和誤差項的經典線性方程，最後利用高斯消元法求解線性方程組。

求解 LWE 的量子算法

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

具體而言：

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

下面三種縮減都是對現有經典多項式時間縮減的微小修改，從標準 LWE 到它們的變體。

1. 有 k 個無誤差座標的 LWE。

2. 有 k 個選擇誤差項的 LWE。

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

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

現在定義一個 q-ary 格，使得找到這個特殊 q-ary 格的唯一最短向量意味着求解。

設：

參數選擇

本小節將介紹更多量子算法中使用的參數。設 D ∈ N + 爲縮放參數。

參數是在以下約束下設置的（）：

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

主要量子算法的詳細概述

本節中，作者運行一個由 9 大步驟組成的量子子程序，時間複雜度爲 O (n) 次。每次運行量子子程序時都會獲得一個經典線性方程，其中隨機係數在中的最短向量上（與 LWE 秘密和誤差向量相關）。因此，運行 O (n) 次後將得到一個滿秩線性方程組，並通過高斯消元法計算 LWE 秘密項和誤差項。

如下爲量子子程序中 9 大步驟的高級描述，包括了每個步驟中獲得的狀態以及經典信息。

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

步驟 1：在上準備一個疊加，並應用復高斯窗。

步驟 2：在 |φ1⟩上應用。

步驟 3：在 |φ_2⟩上應用復高斯窗，得到 |φ_3⟩ 和 z′。

步驟 4：在 |φ_3⟩上應用。

步驟 6：在 |φ_5⟩應用。

步驟 7：提取 |φ_6⟩ 的中心，得到純虛高斯態 |φ_7⟩。

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

在第 8 步中，作者首先執行四次操作，然後進行部分測量，最後將這四次操作反轉（將確保這四次操作是可逆的）。目標是提取 v′_1 mod D^2_p1，最終返回到 |φ_7⟩。也就是說，將學習 v′_1 mod D^2_p1 而不折疊或修改 |φ_7⟩。

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

在第 9 步中，作者的目標是將 |φ_8⟩ 轉換爲秘密上的經典線性方程，最終給出如下主引理（引理 3.8）的證明。步驟 9 使用步驟 8 中獲得的 v′_1 mod D^2_p1 信息，並插入 LWE 秘密中的已知項的 κ-1 座標。

陳一鐳簡介

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

在個人介紹中，陳一鐳的研究成果主要包括設計了格問題的量子算法，建立了多線性映射和代碼混淆在格問題上安全實現的基礎，提出了證明 Fiat-Shamir 假設的方法，以及提出了一個不可逆羣的構造。

也就是說，在 2022 年，陳一鐳就發表了有關格問題的研究。該研究「Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering」發表於 2022 年歐洲密碼大會（Eurocrypt 2022），並收到 Journal of Cryptology 邀稿。

在 2022 年這篇研究中，陳一鐳團隊和普林斯頓大學的劉啓鵬和 Mark Zhandry 提出了一個能解決特殊格問題的多項式時間量子算法。這些特殊格問題是 SIS 和 LWE 的變種。他們雖然並不等價於標準的格問題，但是已經非常接近於密碼學常用的問題。他們的量子算法中使用了一種被稱爲 “過濾” 的方法，是在量子算法的設計中第一次使用，可能爲未來量子算法的設計帶來新的思路。

參考：

https://sqz.ac.cn/password-50

若通過驗證可顛覆美國後量子密碼設計，清華陳一鐳論文破解格密碼

相關資訊