導語:8月6日,國際密碼學界最重要的預印本平臺 Cryptology ePrint Archive 上線了一篇論文,聲稱找到了一個多項式時間的量子演算法,可以解決"二面體陪集問題"(DCP)——順藤摸瓜,這將動搖全球正在部署的後量子密碼標準的數學地基論文。論文上線不到一天,國際知名後量子密碼專家、西交利物浦大學數學物理學院院長丁津泰教授就在 LinkedIn 上給出了自己的判斷:"論文現階段完全談不上紮實"(the paper is not at all solid at this stage)。而這次快速"會診"的一個特別之處在於:丁教授是與 AI 一起完成逐行審查的。
一、發生了什麼
這篇題為《二面體陪集問題的多項式時間量子演算法》(A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem)的論文,作者是亞馬遜雲科技(AWS)密碼學組的 Daniel R. Simon,8月3日提交、8月6日獲准上線,目前標註為"初稿"(Preliminary Draft)論文。
原論文地址:
論文的聲稱可以用一句話概括:如果它是對的,那麼一旦大規模量子計算機建成,目前全世界正在切換的"抗量子"密碼標準,也會被量子計算機攻破論文。
二、為什麼這事值得緊張
大家可能聽說過:量子計算機能破解今天網際網路上主流的 RSA、橢圓曲線等公鑰密碼論文。為此,美國國家標準與技術研究院(NIST)在 2024 年正式釋出了新一代"後量子密碼"(PQC)標準,全球銀行、雲廠商、作業系統都在陸續遷移。
這套新標準的核心數學地基,是所謂的"格問題",尤其是"帶誤差學習"問題(LWE)論文。可以把它想象成一道"加了噪聲的解方程"題:方程本身好解,但每個等式都被摻入了微小的隨機誤差,想從一堆"帶噪聲的線索"裡還原出真正的秘密,目前無論經典計算機還是量子計算機都被認為無能為力。這個"量子計算機也搞不定"的信念,正是後量子密碼的全部意義所在。
而這篇論文聲稱:存在一條量子捷徑論文。作者沿用了著名學者 Regev 在 2004 年提出的思路——當年 Regev 證明,只要能解決一箇中間問題(DCP),就能一路歸約、動搖 LWE 和格問題;但 Regev 的方案裡缺一塊拼圖(需要一個不現實的"子集和預言機")。這篇新論文聲稱用一種新的"位元擦除"技巧補上了這塊拼圖。補上了,鏈條就通了;鏈條通了,LWE 就危險了。
三、丁津泰的判斷:關鍵引理可疑,論文現階段站不住腳
論文上線當天,朗空量子首席科學家、後量子密碼專家丁津泰教授就通讀了論文,並在 LinkedIn 發帖表明態度論文。他寫道:
"我快速讀了這篇論文,直覺是其中一個關鍵引理——引理4——看起來可疑論文。於是我與 ChatGPT 進行了討論,附件就是 AI 協助生成的分析檔案。"
"雖然我沒有核對全部細節,但我的結論是:這篇論文現階段完全談不上紮實論文。另一方面,我很驚訝作者居然沒有用 AI 來檢查自己的論文——在這個 AI 時代,這顯然不太明智。"
丁教授同時公開了那份 AI 協助完成的逐行分析文件以及個人主頁(連結見文末)論文。
四、問題出在哪?一個"抽獎統計"的比喻
那份逐行分析的矛頭,指向論文第 13–15 頁的引理4——整個演算法"能讀出正確答案"的機率保證,全押在這條引理上論文。
展開全文
引理4的論證核心,是一個"球入箱"模型:論文假設某些關鍵數值像"往 n 個箱子裡獨立地扔很多球"一樣隨機、均勻,於是各箱球數幾乎一樣多,演算法就能工作論文。
但分析指出了一個結構性問題:這些"球"在被統計之前,已經被一連串量子測量和"後選擇"(只保留測量結果合格的分支)篩過一遍了論文。打個比方:你想證明一個抽獎箱是公平的,卻只統計了"中過獎的人"的資料——篩選本身就可能扭曲分佈。而論文從頭到尾沒有證明"篩選之後,均勻性和獨立性依然成立",只是直接沿用了篩選之前的漂亮性質。
除此之外,分析還點出兩個各自獨立的硬傷:一是論文斷言某些"溢位位"的干擾"只會讓分佈更均勻",這是缺乏論證的——相關的隨機量相加完全可能互相抵消而不是更均勻;二是證明假設關鍵分組裡沒有故障樣本,這只是一個常數機率事件,卻被用來支撐引理宣稱的"至少 1−1/n 機率"的結論,兩者對不上論文。
分析文件的最終判定是:"引理4按其現有寫法並未得到證明,且這一缺口是結構性的,而非遺漏了某個小的計算論文。"要修復它,需要一個全新的"條件正則性定理"——這不是打補丁,而是要重新蓋一面承重牆。
五、歷史總是押著相似的韻腳
"格密碼被攻破"的宣告,這不是第一次論文。2024 年 4 月,學者陳亦雷(Yilei Chen)的一篇量子演算法論文同樣轟動一時,數天之內就被同行發現第 9 步存在無法修復的錯誤,作者隨即公開確認。密碼學界對這類重磅宣告的態度從來是:先嚴格驗證,再談信不信。目前這篇論文也尚未經過任何同行評審,ePrint 平臺本身不對論文正確性背書。
值得玩味的是這次驗證的速度和方式:過去,這樣一份佈滿量子疊加態表示式的證明,一位專家逐行核查可能要以周計;這一次,丁津泰憑專家直覺鎖定可疑的引理4,再由 AI 完成逐行的技術審查,前後不過幾個小時論文。他那句"作者居然沒先用 AI 查一遍自己的論文",半是調侃,半是給整個學術圈的提醒——在 AI 時代,重磅宣告發出之前,先讓 AI 當一回魔鬼審稿人,可能會成為新的學術禮儀。
後量子密碼的地基這次大機率安然無恙,但"AI 參與前沿數學審稿"的時代,確實已經來了論文。
相關連結
原論文:
