💻 computer science

Centered Arithmetic Is Not Leakage-Neutral: Finite-Noise Optimal Attacks and Minimax Laws for Modular Representations

本文证明了中心化补码掩码在本质上比无符号掩码更容易受到侧信道攻击，并提供了精确的有限噪声最优攻击、一种新的频谱泄漏定律以及证明在大多数实际模数下无符号存储能最小化泄漏的容量界限。

原作者： José Luis Delgado

发布于 2026-08-31

📖 1 分钟阅读☕ 轻松阅读

原作者： José Luis Delgado

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在数字安全的隐秘世界中，保护密钥是一场与无形观察者的持久战。想象一个存放着主密钥的保险库；如果窃贼能够窥视使用该密钥的计算机的功耗或电磁信号，他们就可能窃取秘密。为了阻止这一点，工程师们使用了一种称为“掩码”（masking）的技术。与其直接处理秘密数值，不如将其分解为若干个随机的部分，即“份额”（shares），并分别对这些部分进行计算。只要这些份额保持独立且带有噪声，秘密就会保持隐藏状态。然而，计算机并不在真空中存储这些数字，而是将它们存储为电开关的模式，即“比特”（bits）。计算机选择记录负数的方式——是作为简单的正值，还是采用特定的有符号格式——会改变这些开关的模式。这种选择产生了一个微小的、无意识的信号，或称“泄漏”（leakage），攻击者可能会利用这一点。多年来，研究人员一直在争论使用现代加密中常见的特定负数格式是否安全，或者它是否在暗中泄露信息。

加泰罗尼亚开放大学（Universitat Oberta de Catalunya）的何塞·路易斯·德尔加多（José Luis Delgado）的一项新研究为这场争论给出了明确的答案：存储这些数字的方式至 việc 极其重要，而一种常用方法并不像之前认为的那样安全。该研究聚焦于一种用于保护数据免受未来量子计算机威胁的特定加密类型。在这些系统中，数字通常以“中心化”（centered）格式存储，即负值的二进制代码中包含许多前导“1”，而不是正数所使用的标准“无符号”（unsigned）格式。作者证明，这种中心化格式比无符号格式泄露了更多的信息。通过建立一个关于这些信号在噪声下如何行为的精确数学模型，该研究证明了中心化格式创造了一种独特的、可测量的弱点，攻击者可以利用这一点比使用无符号格式更快地恢复秘密密钥。

研究人员并非仅仅在猜测这种弱点；他们构建了一张完整的、精确的信息泄漏图谱。他们将计算机的存储视为一个传输数据的信道，但带有一个转折：数据被随机噪声所扰乱，就像无线电信号被静电干扰一样。利用先进的统计工具，他们计算了基于观测到的噪声信号得出每一个可能秘密密钥的精确概率。这使得他们能够设计出最高效的攻击方式，即评估每一个候选秘密的时间仅随系统的复杂程度呈轻微增长。他们发现，虽然无符号格式在最基础层面上最大限度地减少了泄漏，但中心化格式引入了一种特定的信号失真，这种失真会随着保护性“份额”数量的增加而变得更加危险。

至关重要的是，这项研究排除了这种泄漏是微不足道或可以在高噪声环境下被忽略的观点。作者证明，对于中心化格式而言，泄漏不仅是一个微小的缺陷，而是一个结构性特征，无论使用多少个随机份额，只要计算机字长（word size）与数值系统不完全匹配，该特征就会持续存在。他们确定了一个精确的阈值：如果计算机字长比持有该数值严格需要的空间多出三个比特，中心化格式就会明显劣于无符号格式。事实上，对于当前全球加密标准中使用的特定数值，中心化格式泄露的信息如此之多，以至于攻击者所需的观测次数会大幅减少。研究通过包括模拟和实际设备物理测量分析在内的现实世界测试证实了这一点，表明这种理论上的弱点直接转化为了实际的脆弱性。

论文还探讨了是否存在一种完美的数字存储方式来消除所有泄漏。研究人员发现，彻底消除信号的唯一方法是使用一种特殊的编码，其中每个数字都以完全相同数量的“开启”开关来存储。虽然这在理论上是可能的，但它比当前系统的实际存储空间需求要大得多。对于现实应用中的标准尺寸，这种完美的编码并不存在。相反，研究提供了一个清晰的定律，描述了泄漏是如何运作的，表明中心化格式创造了一种可预测的误差模式。这种模式如此独特，以至于它允许在两种存储方法之间建立起一种数学上保证的区分，无论噪声水平如何。

这些发现对于安全软件的设计具有直接的影响。研究表明，在基于格（lattice-based）的密码学中使用中心化表示法来处理负数这一普遍做法并非中性的；它会主动损害安全性。作者提供了精确的公式，工程师可以用这些公式来计算任何特定系统配置的风险。他们还提供了一种新的测试安全性的方法，该方法比以往的技术更高效，能够在极短时间内分析复杂的系统。通过证明中心化格式并非“泄漏中性”，这项研究迫使人们重新评估这些关键加密系统的构建方式。它表明，为了实现最高水平的安全性，开发者应该避免使用中心化格式，转而使用无符号替代方案，或者至少要敏锐地意识到其引入的特定漏洞。这项工作是一项严谨、完整的分析，它将关于“表示法”的模糊担忧转化为了对数字风险的精确、可操作的理解。

技术摘要：中心化算术并非泄露中性

问题陈述

在格密码（如 ML-KEM、ML-DSA）的软件实现中，敏感值通过算术掩码进行保护，其中秘密被拆分为模 $q$ 的随机份额之和。虽然该运算在数学上是模运算，但这些份额的物理存储需要选择机器字中的表示形式。通常，份额被存储为无符号残数（在 $[0, q)$ 范围内）或作为补码形式的中心化有符号整数（在 $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$ 范围内）。

尽管这两种编码实现了相同的模算术，但它们的二进制表示显著不同。具体而言，补码中的负整数表现出符号扩展（前导 1），而其无符号对应项则不然。前人的工作利用了这种“符号扩展”效应进行侧信道攻击（例如绝对值预测器）。然而，目前仍缺乏一个全面的理论框架，能够刻画在有限噪声、任意模数以及所有掩码阶数下，这种表示法选择如何影响泄露。本文旨在解决一个基本问题：中心化算术与无符号存储相比是否具有泄露中性？

研究方法

本文采用结合概率论、傅里叶分析和组合数论的严谨数学方法来对侧信道泄露通道进行建模。

有限噪声通道建模： 作者将掩码份额的泄露建模为独立的加性噪声通道。他们通过将问题视为单个份额泄露分布的循环卷积，推导出了掩码和的精确似然度。
傅里叶分析： 分析利用离散傅里叶变换（DFT）将卷积转换为频域中的乘积。这使得推导最优攻击和泄露的谱分解成为可能。
表示法极小极大化（Representation Minimax）： 本研究通过最小化泄露谱的能量来评估不同的 $\mathbb{Z}_q$ “分段”（即表示法）。这涉及比较连续分段（无符号与中心化）以及任意单射二进制码本。
谱分解： 其中的一个关键方法论创新是将中心化补码泄露谱分解为符号扩展项和进位项，从而进行精确的渐近分析。
算法验证： 通过精确计算、使用完整规模 ML-KEM 和 ML-DSA 参数的合成实验，以及对公开物理迹线的分析，验证了理论界限。

核心贡献

1. 最优有限噪声推断

本文证明，通过使用快速傅里叶变换（FFT）计算的循环卷积，可以在拟线性时间 $O(dq \log q)$ 内计算出掩码和的完整似然度。

结果： 这提供了一种最优攻击策略，能够同时评估所有 $q$ 个假设。
充分性条件： 作者推导出了一个精确条件，在该条件下常用的乘积统计量（乘积中心化份额）能够保留所有的似然信息。他们证明，对于任何模数 $q \ge 2$ 且阶数 $d \ge 2$ 的情况，在有限噪声下，乘积统计量都是严格不充分的。全观测包含的信息量（更高的 KL 散度、Rényi 散度等）明显多于乘积统计量。

2. 全局表示法极小极大定律

本文通过优化表示法的选择来最小化泄露：

一阶泄露： 在所有连续分段中，无符号存储（ $[0, q)$ ）是一阶泄露的唯一极小值点，除非模数占据了整个机器字（ $q=2^m$ ），在这种情况下所有分段都是等效的。
高阶泄露： 无符号存储的优越性并非永久的。本文识别出一个精确的“相变”点：对于特定参数（例如 $q=14, \beta=4$ ），中心化存储会成为 $d \ge 4$ 时阶数的唯一极小值点，而无符号存储在低阶时是最优的。
词典序定律： 对于任何有限的表示法族，当掩码阶数 $d \to \infty$ 时，最终的极小值由泄露系数的最小词典序排序谱决定。
恒定权重码本： 对于任意二进制编码，当且仅当码本具有恒定汉明重量时，泄露才会完全消失。本文提供了存在此类码本的锐利容量界限（ $q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$ ），并计算了标准 NIST 模数（例如 $\beta=14$ 对于 $q=3329$ ）所需的最小字宽。

3. 中心化规约泄露定律

本文的核心理论结果是中心化补码泄露的精确谱分解：

分解： 泄露谱被分为宏观的符号扩展项和二进制的进位缺陷。
主导阈值： 本文证明了一个锐利的统一阈值：需要三个额外比特（ $s = \beta - \lceil \log_2 q \rceil \ge 3$ ）才能使中心化存储在第一傅里叶模态上的泄露幅度严格大于无符号存储。具体而言，当且仅当 $s \ge 3$ 时，条件 $D(q, \beta) > 2U(q)$ 成立。
渐近特性： 对于固定的额外宽度，中心化与无符号泄露系数的比值收敛于 $s+1$ 。对于 $q=2^m-1$ 的特殊情况，泄露比值收敛于一个与正切之和相关的常数（ $\kappa \approx 1.81$ ）。
中性性： 中心化算术并非泄露中性。它仅在 $q=2^m$ 且 $\beta=m$ 的精确情况下才是中性的（即与无符号等效）。在所有其他情况下，中心化存储在第一傅里叶模态上（以及通常在低阶掩码下）会导致严格更高的泄露，尽管在特定参数集下它可能成为高阶时的最优表示。

4. 鲁棒性与样本复杂度

鲁棒性半径： 本文定义了加权汉明重量模型的精确鲁棒性半径，表明只要额外宽度至少为 3，中心化与无符号存储之间的严格分离在考虑位敏感度变化时依然成立。
样本复杂度： 提出了一种指数置信度谐波测试。本文证明，中心化攻击与无符号攻击之间的样本复杂度比值随其谱系数比值的 $2d$ 次方缩放。这意味着对于高阶掩码，使用中心化存储所带来的惩罚（由于其在第一模态上的更高泄露）会呈指数级增长，除非特定的参数集使系统处于中心化存储为全局极小值的状态。

结果与验证

合成实验： 针对完整规模 ML-KEM ( $q=3329$ ) 和 ML-DSA ( $q=8380417$ ) 的实现验证了理论样本复杂度因子。对于 $d=3, 4, 6$ ，中心化表示实现相同成功率所需的迹线数明显多于无符号存储，这与推导出的渐近极限一致。
物理迹线： 本文通过对公开的掩码 ML-DSA 实现的物理迹线进行分析验证了结论。符号判定（Sign predicate）达到了 155.73 的 Welch $|t|$ 值和 90.80% 的平衡准确率，证实了理论所预言的符号扩展泄露通道的存在。
算法效率： 所提出的最优攻击（使用基于 FFT 的卷积）在不到 35 秒内成功对 $q=8,380,417$ 的所有假设进行了评分，证明了其实际可行性。

意义

本文从根本上改变了对软件中算术掩码的理解。它表明，机器表示的选择（中心化 vs 无符号）不仅仅是一个实现细节，更是侧信道泄露通道的一个关键组成部分。

驳斥中性论： 作者明确证明了“中心化算术并非泄露中性”。补码表示中固有的符号扩展引入了一种独特的泄露谱，这是无法仅通过掩码来消除的。
设计指南： 本研究为实现者提供了精确且可操作的指南：
- 当额外比特较少（ $s < 3$ ）时，使用无符号存储以获得一阶安全性，因为它是唯一能最小化一阶泄露的表示。
- 意识到中心化存储通常会带来严重的样本复杂度惩罚（由于其在第一模态上的更高泄露），仅在特定参数集下的极高阶数时才会成为最优选择（展示了最优性的相变）。
- 恒定权重码本提供了实现零泄露的理论路径，但需要特定的字宽，这可能与标准硬件约束不符。
理论基础： 通过提供精确的谱定律和有限噪声下的最优性条件，本文填补了理论掩码安全性与实际实现现实之间的鸿沟，为评估和设计抗侧信道格密码系统提供了严谨的基础。