原聲.

世界太吵，來原聲聽播客

Security Cryptography Whatever

AI 證明逼近平方根障礙：格密碼最壞情況仍安全

OpenAI 模型證明 CVP 在 n 的 1/400 次方近似下仍 NP-hard，幾天內被推到平方根；SVP 指數改進到 2^0.7n、McEliece 遭準多項式攻擊，但現實格密碼因維度膨脹和近似因子 gap 暫安全。

格密碼後量子密碼AI 數學密碼分析量子算法McEliece
三組新結果同一周出現，各自牽動複雜度理論、AI 原創性和後量子密碼安全判斷；不聽完會漏掉後半段的機制和數字。

核心論點 · 點時間戳可跳到原聲

4:17

20 年沒動的格難度門檻，被一篇論文推高

CVP 的精確版本早在 80 年代就被證明 NP-hard；90 年代把 NP-hard 推到任意常數甚至 n 的 1/log log n 次方的近似因子，1998 年定型後 20 年沒動。8 月 1 日 OpenAI 的論文用 n 的 1/400 次方這個固定多項式近似因子打破僵局。Chris 強調這不是密碼學實際使用的參數 regime，而是純複雜性理論結果，但它的證明方式——直接從 3SAT 到 CVP 的代數約簡——讓所有人都意外。

— Chris
7:19

平方根障礙就是終點，再進一步理論會崩

Chris 拿到 n 的 1/400 次方後試著讓模型改善，只改進簿記就得到 n 的 1/28 次方，隨後又有人得到 n 的 1/8 次方。幾天內，Twitter 用戶 Mira 通過反覆提示把結果推到任意 n 的 1/2 - ε 次方。平方根是已知的 co-NP 障礙：若平方根近似 CVP 也 NP-hard，會導致多項式層級崩潰，所以 gap 被完全封閉。密碼學使用的近似因子是 n 到 n² 這樣的小多項式，離新的 NP-hard 區域很近，這讓社區對格問題難度的信心增強。

— Chris
11:30

AI 不再只是拼零件，這次走了新路

Chris 說這是第一個讓他覺得真正原創的 AI 數學結果。之前很多 AI 證明是專家把已有件拼起來，AI 只負責找到第一塊多米諾；這個證明則直接從 3SAT 到最近碼字問題再到 CVP，用 Reed-Solomon 碼分別編碼公式和子句，再用約束拼成格實例。他問過編碼複雜度的同行，沒人見過類似路徑。這讓人聯想到 AlphaGo 那種「外星棋手」式的解法，只是所有零件都來自已知數學，但路徑完全不同。

— Chris
19:41

11 年首次改進 SVP，密碼強度紋絲不動

SVP 是給定格找最短非零向量。2015 年以來的精確算法是 2 的 n 次方時間；三天內三篇 ePrint 獨立把指數常數壓到 0.7 左右，都用了同一套技術，部分論文承認 AI 參與了核心想法。這是 11 年來首次改進。但 Chris 說它幾乎不影響現實密碼學，因為攻擊的是最壞情況精確 SVP，而啟發式算法本來就能做得更好，安全估計不依賴這個精確指數。

— Chris
27:56

號稱破解格密碼的量子論文有實質錯誤

Shor 算法本質上是解循環群上的隱藏移位問題；dihedral 群是循環群加一個翻轉，量子算法長期解不了。把格問題歸約到巨大 dihedral 群的隱藏移位後，若多項式時間解 DCP 就能破所有基於格的密碼學。新論文聲稱做到，但 Chris 說社區發現證明裡有多處實質性錯誤，不像容易修。他打了比方：如果範式真的成立，就像整座房子都著火了，不用糾結溫度具體是多少度。

— Chris
36:12

McEliece 新攻擊不只區分公鑰，還能解密

Classic McEliece 的新攻擊給出一個準多項式時間（n 的 log n 次方）distinguisher，能區分公鑰和隨機串；具體參數下運行時間約 2 的 100 多次方。更重要的是他們能把 distinguisher 變成解密：把密文接到公鑰上跑 distinguisher，輸出會暴露錯誤向量的每一位，從而恢復消息。解密也要準多項式時間並依賴一些 heuristics。論文明確說同樣的思路理論上可用來從公鑰恢復私鑰，但留待未來。

— Chris
45:26

McEliece 的可疑感不是錯覺，只是缺解釋

Chris 解釋為什麼社區長期對 McEliece 有「總覺得有點可疑」的 vibe：多年來幾乎所有變體——換碼、縮小密鑰——都被攻破，唯獨原始 McEliece 還站著，但沒人能給出深層解釋。攻擊思路也一直窄化到 information set decoding 變體。這次結果來自一個做 doubly efficient PIR 的隱私研究組，他們在構造中遇到屏障，發現自己的代數幾何工具能破 McEliece。這證明不同數學視角能帶來突破，但也加深了對 McEliece 安全基礎的不安。

— Chris

原話 · 已逐字校驗

So now we have this like total phase change, you know, up to square root n, but not quite is NP at square root n and beyond. You have, you know, very good reason to think it's not NP-hard. And so we went from like this huge unknown gap to like completely closed gap in a matter of a few days with just miles poking on things. I mean, that's insane.

所以現在我們經歷了一個完全的相變：直到 n 的平方根、但還差一點點的近似因子都仍是 NP 難的；而在平方根及其以上，有充分理由認為不是 NP 難的。我們從巨大的未知空隙，變成幾天之內就完全閉合了空隙，靠的只是 Mira 在模型上戳來戳去。這太瘋狂了。

Chris7:19

I don't, I don't think that's, that's going to be even true, much less do I expect it. And then, so it just completely changed our understanding of these problems.

我不認為這會是真的，更不用說我會預期它。結果它徹底改變了我們對這些問題的理解。

Chris10:28

And it's just unlike anything I've ever seen. I asked some people around, and they hadn't seen it either.

它完全不像我見過的任何東西。我問了周圍一些人，他們也沒見過。

Chris12:32

So the reason it doesn't kind of move the needle on that, which is a great question, is that these worst case to average case reductions usually have a blow up in the dimension to some amount.

所以它沒有真正改變那個問題（安全估計）的原因——這是一個很好的問題——是這些最壞情況到平均情況的歸約通常會在維度上產生一定程度的膨脹。

Chris22:44

if that paradigm had worked out if that algorithm had actually been correct and correct analysis we're quibbling over the approximation factor

如果那個範式真的成立、那個算法真的正確且分析正確，那麼我們糾結的只是近似因子而已。

Chris31:00

數字與實體

OpenAI 證明的 CVP 近似因子n 的 1/400 次方4:17
幾天後 CVP 近似因子被推到任意 n 的 1/2 - ε7:19
精確 SVP 最佳算法時間（2015 年起）約 2^n19:41
新 SVP 算法指數約 2^0.7n19:41
SVP 上次改進距今11 年20:42
McEliece distinguisher 複雜度準多項式 n^{log n}35:12
McEliece distinguishing 具體運行時間約 2 的 100 多次方36:12

術語

CVP最近向量問題
給定格與目標點，找距離最近的格點；近似版本允許因子誤差。
SVP最短向量問題
在格中找最短的非零向量，是格密碼核心難題。
Dihedral coset problem二面體陪集問題
在二面體群上求解隱藏移位，與格問題歸約相關的量子難題。
Reed-Solomon code裡德-所羅門碼
一種代數糾錯碼，新 CVP 證明用來編碼 3SAT 公式。
Information set decoding信息集解碼
攻擊 McEliece 類密碼的傳統方法，通過猜測信息集解碼。
Doubly efficient PIR雙高效私密信息檢索
服務端計算快、通信量小的私密信息檢索，這項研究的來源。

收聽指南

誰該聽

做後量子密碼選型和 FHE 落地的工程師、想判斷 AI 數學能力的投資人，以及關心格密碼最新攻擊的研究者。

可跳過

最後 2 分鐘密歇根橄欖球閒聊和廣告可跳過，其餘全程高濃度。