本论文针对后量子密码(PQC)硬件实现中的掩码Barrett reduction的侧信道泄漏问题,提出首个通用且机器验证的基数界限——1-Bit Barrier。Barrett reduction是基于NTT的PQC实现(如ML-KEM、ML-DSA)的非线性核心,但现有组合框架(ISW、t-SNI、PINI、DOM)仅针对GF(2)上的布尔掩码,无法直接应用于素域上的算术掩码。作者基于此前系列工作(QANARY、partial-NTT-masking margins、代数基础、蝴蝶组合),填补了这一空白。核心贡献在于:1)证明对于任意模数q>0和移位s,Barrett内部导线映射f_x(m) = ((x + 2^s - m) mod 2^s) mod q的原像基数属于{0,1,2},绝不超过2——这一性质被称为1-Bit Barrier,意味着每条内部导线最多泄露1比特的最小熵;实际泄漏通常更少,因为计数为0的情况(不可达输出值)使界更为保守。2)引入PF-PINI(素域PINI)概念,证明Barrett满足PF-PINI(2),Cooley-Tukey蝶形运算满足PF-PINI(1),并观察到在阶段间加入新鲜掩码时,组合管线的最大原像基数为max(k1, k2),因此1-Bit Barrier可传播。3)在Lean 4(Mathlib)中完成了12条定理的机器验证,无一个“sorry”,结果对所有q>0通用。4)指出Adams Bridge因缺少阶段间新鲜掩码而违反PF-PINI组合,解释了此前发现漏洞的原因。该工作为NIST IR 8547推荐的形式化方法在PQC实现验证中提供了首个通用机器验证的基数界,并给出1比特泄漏的直观解释。适合侧信道分析、PQC硬件安全、形式化验证领域的研究者和工程师阅读。
💡 推荐理由: 为后量子密码掩码实现提供了首个通用、机器验证的侧信道泄漏上界,直接适用于ML-KEM和ML-DSA,填补了素域算术掩码分析的理论空白,有助于指导安全硬件设计。
🎯 建议动作: 研究跟进