PQC Barrett Reduction 論文閱讀分析：很多硬體安全真正缺的，不是更多 masking，而是先證明最危險那段到底最多漏多少
本文由 AI 產生、整理與撰寫。
論文基本資訊
- 論文標題：Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware
- 作者：Ray Iskander、Khaled Kirah
- 年份：2026
- 來源：arXiv:2604.24670
- 論文連結：https://arxiv.org/abs/2604.24670
- DOI：10.48550/arXiv.2604.24670
- 主題：PQC Hardware Security、Masked Barrett Reduction、Side-Channel Leakage、Formal Verification、Lean 4、ML-KEM / ML-DSA
如果你最近一路看過 sectools.tw 前面幾篇關於 PQC masking、pre-silicon verification、還有「很多硬體安全真正卡住的，不是有沒有做 masking，而是 tape-out 前根本證不出它沒漏」那條線，這篇 Machine-Checked Cardinality Bounds for Masked Barrett Reduction 很值得接上。
很多 PQC 硬體真正缺的，不是再多一層 masking，而是先把最危險的非線性核心到底最多會漏多少，正式證成一個能跨參數、跨模數、跨實作討論的上界。
這篇論文瞄準的不是整顆 ML-KEM / ML-DSA 晶片，而是裡面一個很關鍵、也很容易成為 side-channel 分析焦點的地方：Barrett reduction。作者的論點很硬：與其一直靠 case-by-case attack / defense 經驗猜這一段「大概」安全，不如直接問一個更根本的問題——在 first-order arithmetic masking 與 probing model 下，這個內部 wire map 的可觀測輸出，最多對 secret 造成多少資訊收縮？
這篇在解什麼問題？
Barrett reduction 是 practical NTT-based PQC implementation 裡非常常見的 nonlinear core。問題也正出在這裡：很多 masking composition framework 比較擅長處理的是 Boolean masking over GF(2)，但 Barrett reduction 這類 prime-field arithmetic、modular reduction、內部線路映射比較複雜的東西，常常落在一個尷尬區間：
- 你知道它重要
- 你知道它可能漏
- 你甚至可能知道某些設計會出事
- 但你沒有一個 machine-checked、可泛化的 leakage characterization
這代表很多討論最後都會退回成：
- 這組參數下看起來沒爆
- 那個模數下 attack 沒成功
- 這版 masking margin 好像夠
- 某個 bridge / composition 似乎合理
而這正是硬體安全最不舒服的地方。因為沒有形式化上界，你就很難分清楚自己是在證安全，還是在累積還沒撞牆的經驗。
核心貢獻：作者把 Barrett reduction 的 leakage 問題改寫成 cardinality 問題
這篇最漂亮的地方，是它沒有直接從「功耗大概長什麼樣」那種類比直覺下手，而是把 Barrett 內部 wire map 抽象成一個數學對應：
f_x(m) = ((x + 2^s - m) mod 2^s) mod q
作者想證明的是：對任意 q > 0 與 shift s，這個映射的 preimage cardinality 只會落在 {0, 1, 2}，不會再大。
這個結果乍看很數學，但安全意義非常直接：
- 若某個可見 internal wire value 最多只對應到 2 個可能輸入
- 那代表它造成的 min-entropy loss 最多就是 1 bit
- 而且這個上界是 universal over all moduli
作者把這件事命名成 1-Bit Barrier。白話一點講，就是：
不是說 Barrett reduction 完全不漏，而是至少你現在有一個 machine-checked 的硬上界：單一 internal wire 在這個模型下，最多就漏到這裡，不會再更糟。
這種結論的價值，不在於它把風險歸零，而在於它把原本模糊的「可能有 leakage」改寫成可被正式推理、可被組合討論、可作為工程設計邊界的量化敘述。
這篇真正補的洞：不是 attack demo，而是可組合的 leakage accounting
很多 side-channel 論文最容易讓人有感的，是直接把某個實作打穿；但這篇更像是在補基礎建設。作者不是只想證明某一版 Barrett 還可以，而是想把它放進一個可組合的 formal vocabulary 裡。
因此他們提出了 PF-PINI（Prime-Field PINI）：
- Barrett satisfies PF-PINI(2)
- Cooley-Tukey butterfly satisfies PF-PINI(1)
這些符號真正重要的不是名字，而是它在說：我們終於可以不用只靠「這段大概安全」來接 pipeline，而是能把每一段的 leakage multiplicity 當成一個可被帶著走的性質。
作者還進一步觀察到——雖然尚未完成正式證明——若 stage 間有 fresh inter-stage masking，組合後的 max-multiplicity 可能可由 max(k1, k2) 來界定。這意味著 1-Bit Barrier 不是只活在一個孤立元件裡，而是有機會沿著 pipeline 傳播。
這正是很多硬體 masking 論文真正稀缺的東西：不是單點安全故事，而是 composition story。
Lean 4 / Mathlib 在這篇裡不是裝飾，而是論文本體
另一個不能跳過的重點，是這篇不是口頭說「我們有形式化」，而是真的把關鍵 cardinality 結果 machine-check 在 Lean 4 with Mathlib 裡。論文摘要直接寫得很硬：
- 12 proved results
- zero sorry
- universal over all q > 0
這裡最值得注意的是 zero sorry。因為在 Lean 社群裡，sorry 基本上就是「先假裝這裡證過了」。作者特別強調沒有這種暫留洞口，等於是在說：這不是半成品 proof sketch，而是你可以真的拿來當 assurance artifact 看待的機器驗證結果。
對 PQC implementation assurance 來說，這種東西的價值會越來越高。尤其當 NIST IR 8547 已經在推 formal methods for PQC implementation validation，產業和研究圈遲早都得面對一件事：未來不只要說你有 masking，還要說你怎麼證這份 masking 的關鍵部件真的守得住。
作者也順手回答了：為什麼有些前作會翻車
摘要裡另一個很有用的點，是作者把先前系列工作裡發現的漏洞，和這篇新框架接了回來。特別是他們指出 Adams Bridge 缺少 fresh inter-stage masking，因此違反 PF-PINI composition，這也解釋了為什麼前兩篇 paper 會挖出漏洞。
這種回填很重要，因為它讓這篇不是一個漂浮的新理論，而是能拿來重讀既有失敗案例的 framework。也就是說：
- 以前知道某個 bridge 有洞
- 現在比較清楚它是在哪個 composition 假設上失手
- 而不是只停在「實驗上看到會漏」
很多形式化安全工作真正珍貴的，不是替成功案例背書，而是替失敗案例找出可重用的失敗語言。
這篇論文真正的 framing：很多 PQC 硬體安全缺的不是更多 masking，而是 leakage budget discipline
我覺得這篇最該帶走的，不是某個式子或某個新縮寫，而是它把問題重心拉得很對：
很多 PQC 硬體真正缺的，不是再多一個 masking trick，而是先把每個 nonlinear 核心到底能漏到哪裡，變成可計算、可組合、可被機器檢查的 leakage budget discipline。
這跟不少硬體 security 真正的成熟路徑很像。產線不怕你有局部 intuition，怕的是你沒有 system-wide accounting。今天你若連 Barrett reduction 這種核心都還在靠經驗猜 margin，那到 NTT pipeline、butterfly stages、bridge composition、最後整顆 accelerator tape-out 時，你就很難說自己是在做 assurance，而不只是做 hopeful engineering。
當然，這篇也有邊界
這篇很強，但它也不是把整件事做完。
- 它給的是 first-order probing model 下的 machine-checked cardinality bound，不是所有 leakage model 的終局答案。
- PF-PINI 的某些 composition propagation 還停在 observation，而非完整 proof。
- 這篇聚焦的是 Barrett reduction 與相關組件，不是整個 PQC datapath 已完全端到端 formalized。
- min-entropy 上界很有價值，但真實實作上的 physical leakage behavior 還是需要和實驗面互補。
但這些邊界不太構成缺點，反而更像它下一步該往哪裡走的清單。因為作者其實已經把最關鍵的地基打出來了：先把一個一直被視為麻煩核心的 nonlinear reduction，正式收編進 machine-checked leakage reasoning。
結語
Machine-Checked Cardinality Bounds for Masked Barrett Reduction 這篇論文最值得記住的，不是它替 PQC hardware 說了一句「大致安全」，而是它替一個長期很模糊的問題，硬生生釘出了一條正式邊界：Barrett reduction 在這個模型下，單一 internal wire 的 leakage multiplicity 不會超過 2，因此對應到最多 1 bit 的 min-entropy loss。
這種結果的真正意義，是把「看起來像安全」往「可被機器驗證的安全會計」再推一步。對 ML-KEM、ML-DSA 這種會真的進標準、進硬體、進供應鏈的 PQC 實作來說，這比再多一個 ad hoc masking patch 更有長期價值。
很多 PQC 硬體真正缺的，不是更多安全直覺，而是讓安全直覺終於變成一份機器看得懂、參數族扛得住、組件間接得起來的證據。