MoRo：从单样本环上带错学习(Ring-LWE)舍入密钥交换到模上带错学习(Module-LWE) IND-CCA 密钥封装机制(KEM)

《Sensors》：MoRo: From One-Sample Ring-LWE Rounding Key Exchange to Module-LWE IND-CCA KEM

　　

随着物联网(IoT)与传感器网络环境对长期安全通信需求的不断增长，实用且稳健的后量子密钥建立机制变得日益重要。本研究重新审视了ACNS 2019提出的仅临时Ding密钥交换(DKE)，该方案基于单样本带舍入的环上带错学习(Ring-LWE)，原始分析仅覆盖被动安全性。在DKE框架基础上，研究人员提出了MoRo-KEM，一种基于模上带错学习(Module-LWE)并使用舍入的密钥封装机制(KEM)。首先，研究人员将构造从Ring-LWE设定提升(lift)至Module-LWE设定，在保留环级别效率的同时实现了更灵活的参数量选择，并降低对刚性代数结构的依赖。其次，研究人员用中心二项分布(CBD)替代秘密与错误的离散高斯采样，从而简化常数时间向量化实现，同时保持所需噪声行为。第三，研究人员将所得密钥交换核心扩展为IND-CPA安全的公钥加密(PKE)方案，并通过Fujisaki–Okamoto(FO)变换进一步获得IND-CCA安全的KEM。最后，在安全级I下，MoRo-KEM达到2-166的解密失败率，低于CRYSTALS-Kyber报告的2-139，从而提升了对解密失败攻击的稳健性。这些特性使所提设计在计算、内存与通信预算受限的传感器节点、边缘设备与网关间的安全密钥建立中具有吸引力。总体而言，该构造提供了一条从临时密钥交换到实例化于Module-LWE上的实用IND-CCA安全KEM的具体路径。

论文解读如下。该研究发表于《Sensors》（MDPI）。研究背景方面，物联网(IoT)与传感器网络由大量资源受限设备构成，需在长期运行下保障机密性与认证密钥建立，但Shor算法表明大型量子计算机可多项式时间破解基于整数分解与离散对数的经典公钥密码（如RSA、Diffie–Hellman、ElGamal），因此后量子密码(PQC)尤其是格基密码成为重要方向。现有方案中，非结构化LWE密钥过大，结构化Ring-LWE（如NewHope、Ding密钥交换DKE）效率高但代数结构刚性强、参数量不灵活；Module-LWE（如CRYSTALS-Kyber）介于两者之间，已成为NIST PQC标准化重点。但Kyber参数紧密绑定数论变换(NTT)友好设计，灵活性受限；其AES-128安全级下解密失败率高于2^-139，解密失败可能成为攻击面；DKE本身仅具被动安全的临时密钥交换，未达IND-CPA/IND-CCA安全。为兼顾实现效率、参数灵活性、低解密失败率与强安全 notion，并在资源受限IoT场景部署，研究人员开展了将单样本Ring-LWE舍入密钥交换提升为Module-LWE下IND-CCA安全KEM（MoRo-KEM）的工作，结论是通过Module-LWE提升、CBD采样替代、PKE扩展与FO变换，在AES-128安全级实现2^-166解密失败率，且C语言实现在Intel Xeon上性能可比拟Kyber，对IoT安全通信有重要意义。

主要关键技术方法包括：1）基于Ding密钥交换(DKE)框架，将构造从Ring-LWE提升(lift)至Module-LWE设定，保留环多项式运算效率同时使用模秩k向量结构以增加参数灵活性并减弱对理想格刚性结构的依赖；2）使用中心二项分布(CBD)采样秘密向量s与错误向量e，替代离散高斯采样，便于常数时间、向量化实现且保持噪声界限与方差；3）复用DKE的舍入(Round)、恢复(Recover)、提示(Hint)、信号(Signal)、调和(Reconciliation)函数并适配Module-LWE系数域，实现带误差容忍的共享值提取；4）由Module-LWE密钥交换核心构造IND-CPA安全公钥加密(MoRo.CPA-PKE)，再应用Fujisaki–Okamoto(FO)变换得到IND-CCA安全KEM(MoRo.CCA-KEM)；5）参数选取结合NTT兼容性与解密失败概率分析（通过Python仿真误差分布），用LWE Estimator（2016代价模型）评估Module-LWE最佳攻击代价以满足NIST安全级I（AES-128位）；6）实现层面采用C语言（gcc 8.5.0），多项式生成由种子经可扩展输出函数(XOF)派生，对称原语含PRF、XOF、哈希、KDF。

研究结果如下。第2节预备知识：研究人员固定符号，设模q为奇素数、p为小模、n为2的幂、k为模秩，多项式环R_q=Z_q[x]/(xⁿ+1)；定义CBD_η为中心二项分布支撑在[-η,η]的整数分布，均匀分布U(S)；对称原语含PRF:G→{0,1}^?、XOF:S→{0,1}^*、哈希H:{0,1}^*→{0,1}^?、KDF；形式化定义搜索与判定版本LWE、Ring-LWE、Module-LWE问题，并明确Module-LWE假设为PPT敌手难区分样本与均匀随机。

第3节密码学背景：研究人员回顾Ding密钥交换(DKE)的临时Ring-LWE+舍入机制，详述Hint函数HInt_q,p(x)、Signal函数S(x)、调和函数Rec(x,w)（误差容忍ε=(q-1)/2p）、舍入函数Round_q,p(x)（Algorithm 1，按奇偶与边界随机修正保奇偶）、恢复函数Recover_q,p(x)（Algorithm 2），以及由128位种子经XOF派生多项式系数（Algorithm 3）；同时回顾CRYSTALS-Kyber结构：由Module-LWE构造IND-CPA的PKE再通过FO变换得IND-CCA KEM，给出KeyGen、Enc、Dec算法（Algorithms 4–6）。

第4节我们的方案：研究人员提出设计路径，先构建MoRo.CPA-PKE（Algorithms 7–9）：KeyGen采样CBD秘密s_i∈R_q^k、错误e∈R_q^k，公钥t=A s+e（A由种子经XOF生成），私钥为s；加密输入消息m（编码为多项式μ∈R_q），采样r,e₁,e₂～CBD，计算u=A^Tr+e₁，v=t^Tr+e₂+μ·?q/2?，输出密文(u,v)；解密输入(u,v)，计算μ′=v-s^Tu，经Recover与调和得m′。研究人员证明正确性：由v-s^Tu=2e₂^Ts+e₁^Ts+e₂·?q/2?+μ·?q/2?，误差项为偶数，舍入/恢复保奇偶，若总误差∞-范数<q/(2p)则调和一致，解密失败率δ=Pr[‖误差‖_∞≥q/(2p)]，误差来自CBD线性组合，各分量取对称偶数值概率均等。接着研究人员给出MoRo.CCA-KEM（Algorithms 12–14）：KeyGen调用CPA-PKE.KeyGen并打包哈希公钥等；Enc(pk)采样随机msg m，计算c=CPA-PKE.Enc(pk,m)，K=KDF(m,c)，输出(K,c)；Dec(sk,c)解密m′=CPA-PKE.Dec(sk,c)，重加密c′=CPA-PKE.Enc(pk,m′)，若c′=c则K=KDF(m′,c)否则K=KDF(z,c)（z为sk中随机数），FO验证式解密防CCA攻击。

第5节安全性：研究人员给出IND-CPA的游戏序列证明（Game₀真实IND-CPA实验→Game₁CBD由PRF生成→Game₂A由XOF均匀→Game₃t=A s+e中(A,t)替换为均匀Module-LWE样本→Game₄替换u=A^Tr+e₁中(A,u)为均匀→Game₅调和位w=Signal(·)因输入均匀故w均匀→Game₆挑战密文整体均匀），引理5表明PRF替代真随机可忽略优势，引理6的XOF建模随机预言机使Game₁与Game₂同分布，引理7–8基于Module-LWE困难归约Game₂→Game₃、Game₃→Game₄的优势可忽略，引理9由引理3（Round输出均匀若输入均匀）得w均匀故Game₄与Game₅同分布，引理10的FO式掩码项H(m‖w)在公开视图下伪随机故挑战密文可替换为均匀（Game₅→Game₆）；定理1综合得IND-CPA安全可归约至PRF安全与Module-LWE困难。继而定理2在随机预言模型(ROM)下引用Hofheinz等的FO变换标准定理，得IND-CCA优势Adv_CCA≤2·Adv_CPA+(q_RO+1)·δ，δ为解密失败率；定理3在量子随机预言模型(QROM)下引用标准QROM FO分析得Adv_CCA≤2·Adv_CPA+(2q_RO)^1/2·δ+…。

第6节参数集：研究人员选取n=256，q=3329（NTT友好），p=2（舍入模），考虑k=2,3,4与CBD参数η=2,3,4；通过Python仿真解密失败率，主参集(k=3,η=3)得δ≈2^-166（AES-128安全级），低于Kyber512的≈2^-139；用LWE Estimator（sieving代价β²·logβ）估计最佳BKZ块大小β，确认安全级I（≥2¹²⁸操作）。公钥尺寸为k·n·log₂q比特，密文为(n+k·n)·log₂q比特；C语言实现于Intel Xeon Gold 6240@2.60GHz（gcc 8.5.0），MoRo.CCA-KEM的KeyGen、Enc、Dec中位数周期分别为约X、Y、Z周期（与Kyber同环境可比，具体数值见原文表3），显示实用效率。

第7节结论：研究人员总结构造了基于DKE的PKE并证IND-CPA安全，应用FO变换得IND-CCA KEM，参数集在AES-128安全级下达2^-166解密失败率，实现验证效率，适合IoT/传感器网络下受限设备的后量子密钥建立；该工作提供了从临时密钥交换到Module-LWE上实用IND-CCA KEM的具体路径，兼具理论扩展与实践意义。

讨论与结论翻译：研究人员首先在DKE机制基础上构造了公钥加密(PKE)方案并证明其IND-CPA安全性；随后通过对该PKE应用轻微变形的Fujisaki–Okamoto(FO)变换获得了密钥封装机制(KEM)并证明了其IND-CCA安全性；此外，研究人员提出了在达成AES-128位安全的同时实现低至2^-166的解密失败率的参数集；研究人员还实现了所提方案并评估了性能，论证了其实际效率。除核心密码学贡献外，结果还表明MoRo-KEM与物联网及传感器网络环境的后量子保护相关：此类场景下需在计算、内存、通信受限下实现安全密钥建立，且需在大批量分布式设备中保持稳健性；Module-LWE的效率、实现友好的采样与低解密失败率的组合使该方案成为传感器节点、边缘设备与网关间长期系统抗量子攻击的有意义候选；因此该构造不仅是对DKE的有用理论扩展，也为IoT与安全传感应用提供了实用的后量子设计方向。