从信息熵到格密码：手把手推导Renyi散度在LWE问题中的一个关键上界

从信息熵到格密码手把手推导Renyi散度在LWE问题中的一个关键上界在密码学研究中格密码Lattice-based Cryptography因其抗量子计算攻击的特性而备受关注。其中基于错误学习Learning With Errors, LWE问题的加密方案是格密码体系中的重要组成部分。本文将聚焦于一个具体而关键的技术细节如何利用Renyi散度Renyi Divergence证明噪声分布的微小偏移不会破坏LWE方案的安全性。1. 预备知识从信息熵到Renyi散度1.1 信息熵的基本概念信息熵是量化信息不确定性的核心工具。香农熵Shannon Entropy定义为$$ H(X) -\sum_{x \in \mathcal{X}} p(x) \log p(x) $$而Renyi熵作为其推广形式引入了阶数order参数α$$ H_\alpha(X) \frac{1}{1-\alpha} \log \left( \sum_{x \in \mathcal{X}} p(x)^\alpha \right) $$当α→1时Renyi熵退化为香农熵α2时称为碰撞熵Collision Entropy。1.2 Renyi散度的定义与性质对于两个离散概率分布P和Q且supp(P) ⊆ supp(Q)其α阶Renyi散度为$$ D_\alpha(P||Q) \frac{1}{\alpha-1} \log \left( \sum_{x \in \mathcal{X}} \frac{P(x)^\alpha}{Q(x)^{\alpha-1}} \right) $$关键性质单调性对于α₁ α₂有D_α₁(P||Q) ≤ D_α₂(P||Q)数据处理不等式对任意函数fD_α(P^f||Q^f) ≤ D_α(P||Q)概率传递性若D_α(P||Q) ≤ λ则对任何事件E有P(E) ≤ (Q(E))^{(α-1)/α} e^{λ(α-1)/α}2. 离散高斯分布在格密码中的应用2.1 离散高斯分布的形式化定义在格密码中m维离散高斯分布记作$$ D_{\mathbb{Z}^m, \sigma} : \text{关于原点对称的离散高斯分布} $$其概率质量函数为$$ \forall x \in \mathbb{Z}^m, \quad D_{\mathbb{Z}^m, \sigma}(x) \frac{e^{-|x|^2/(2\sigma^2)}}{\sum_{y \in \mathbb{Z}^m} e^{-|y|^2/(2\sigma^2)}} $$2.2 偏移离散高斯分布给定偏移向量e ∈ ℤᵐ定义偏移后的分布$$ D_{\mathbb{Z}^m, \sigma, e}(x) D_{\mathbb{Z}^m, \sigma}(x - e) $$在LWE问题中这种偏移可能代表敌手对噪声分布的微小扰动。3. Renyi散度的关键上界推导3.1 问题设定我们需要证明当σ足够大时偏移分布D_{ℤᵐ,σ,e}与原分布D_{ℤᵐ,σ}的2阶Renyi散度存在上界$$ D_2(D_{\mathbb{Z}^m, \sigma, e} || D_{\mathbb{Z}^m, \sigma}) \leq \frac{2|e|^2}{\sigma^2} $$3.2 详细推导步骤展开Renyi散度定义$$ D_2(P||Q) \log \left( \sum_{x \in \mathbb{Z}^m} \frac{P(x)^2}{Q(x)} \right) $$代入具体分布表达式$$ \log \left( \sum_{x \in \mathbb{Z}^m} \frac{e^{-|x-e|^2/\sigma^2}}{e^{-|x|^2/(2\sigma^2)}} \cdot \frac{1}{Z_\sigma} \right) $$其中归一化因子Z_σ ∑_{y∈ℤᵐ} e^{-‖y‖²/(2σ²)}。简化指数部分利用恒等式‖x-e‖² ‖x‖² - 2⟨x,e⟩ ‖e‖²可得$$ \frac{e^{-|x-e|^2/\sigma^2}}{e^{-|x|^2/(2\sigma^2)}} e^{-|x|^2/(2\sigma^2) 2⟨x,e⟩/σ^2 - |e|^2/σ^2} $$利用高斯分布的矩生成函数对于D_{ℤᵐ,σ}有$$ \mathbb{E}[e^{2⟨x,e⟩/σ^2}] \leq e^{2|e|^2/σ^2} $$最终上界计算综合以上步骤可得$$ D_2(P||Q) \leq \log \left( e^{2|e|^2/σ^2} \right) \frac{2|e|^2}{σ^2} $$3.3 参数选择的意义当σ poly(n)且‖e‖ O(1)时$$ \frac{2|e|^2}{\sigma^2} O(1/\text{poly}(n)) $$这意味着在渐进意义下该Renyi散度是可忽略的从而保证了安全性。4. 在LWE安全性证明中的应用4.1 安全性归约中的关键步骤在标准LWE问题中敌手需要区分以下两种分布(A, A·s e) 其中e ← D_{ℤᵐ,σ}(A, u) u为均匀随机向量当敌手试图通过微小扰动如添加偏移量e来破坏方案时利用Renyi散度上界可以证明若原始分布与扰动分布的Renyi散度可忽略则敌手的优势增加也可忽略。4.2 实际应用中的参数设置考虑具体实现时的参数选择参数安全要求典型取值维度m抵抗格约简攻击≥512模数q保证LWE困难性≈2³²噪声σ控制Renyi散度≥8√q在实际方案设计中常取σ Ω(√(n log q))以保证足够的安全性裕度。5. 扩展讨论与其他散度度量的比较5.1 与KL散度的关系KL散度Kullback-Leibler Divergence可视为α→1时的Renyi散度极限情况。但在密码学证明中KL散度适用于单次采样场景的概率分析Renyi散度特别适合多次采样场景的紧致分析5.2 统计距离的局限性统计距离Statistical Distance虽然直观但在处理高斯分布时# 计算两个离散高斯分布的统计距离伪代码 def statistical_distance(P, Q): return 0.5 * sum(abs(P(x) - Q(x)) for x in support)对于σ较大的情况统计距离可能过于宽松而Renyi散度能提供更精确的控制。6. 实现注意事项与常见误区6.1 采样精度的影响在实际实现离散高斯采样时需注意截断误差必须设置适当的截断参数T τσ通常τ ≥6精度要求计算指数函数时需要至少κ-bit精度其中κ Ω(log σ)6.2 典型错误案例错误1低估σ导致Renyi散度过大后果安全性证明失效错误2忽略归一化因子的计算误差后果实际分布偏离理论模型在最近的NIST后量子密码标准候选方案中Kyber和Dilithium都采用了类似的技术路线。例如Kyber设置σ √(k/2)·η其中η为安全参数通过精确控制Renyi散度来保证即使存在微小扰动方案仍保持IND-CCA2安全性。