💻 computer science

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

This paper demonstrates that centered two's-complement arithmetic masking is inherently more vulnerable to side-channel attacks than unsigned masking, providing exact finite-noise optimal attacks, a new spectral leakage law, and capacity bounds that prove unsigned storage minimizes leakage for most practical moduli.

Original authors: José Luis Delgado

Published 2026-08-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: José Luis Delgado

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the hidden world of digital security, protecting secret keys is a constant battle against invisible observers. Imagine a vault that holds a master key; if a thief can peek at the power consumption or electromagnetic signals of the computer using that key, they might steal the secret. To stop this, engineers use a technique called masking. Instead of handling the secret number directly, they break it into several random pieces, or "shares," and perform calculations on these pieces separately. As long as the shares remain independent and noisy, the secret stays hidden. However, a computer does not store these numbers in a vacuum; it stores them as patterns of electrical switches, known as bits. The way a computer chooses to write down a negative number—whether as a simple positive value or as a specific signed format—changes the pattern of these switches. This choice creates a tiny, unintended signal, or "leakage," that an attacker might exploit. For years, researchers debated whether using a specific format for negative numbers, common in modern encryption, was safe or if it secretly gave away information.

A new study by José Luis Delgado at the Universitat Oberta de Catalunya settles this debate with a definitive answer: the choice of how to store these numbers matters deeply, and a common method is not as safe as previously thought. The research focuses on a specific type of encryption used to protect data against future quantum computers. In these systems, numbers are often stored in a "centered" format, where negative values are represented with many leading ones in their binary code, rather than the standard "unsigned" format used for positive numbers. The author demonstrates that this centered format leaks significantly more information than the unsigned alternative. By developing a precise mathematical model of how these signals behave under noise, the study proves that the centered format creates a distinct, measurable weakness that an attacker can exploit to recover secret keys much faster than with the unsigned format.

The researchers did not just guess at this weakness; they built a complete, exact map of the information leakage. They treated the computer's storage as a channel that transmits data, but with a twist: the data is scrambled by random noise, just as a radio signal is distorted by static. Using advanced statistical tools, they calculated the exact likelihood of every possible secret key based on the noisy signals observed. This allowed them to design the most efficient possible attack, one that evaluates every candidate secret in a time that grows only slightly with the complexity of the system. They found that while the unsigned format minimizes the leakage at the most basic level, the centered format introduces a specific type of signal distortion that becomes more dangerous as the number of protective "shares" increases.

Crucially, the study rules out the idea that this leakage is negligible or that it can be ignored if the noise is high. The author proved that for the centered format, the leakage is not just a minor flaw but a structural feature that persists regardless of how many random shares are used, provided the computer word size is not perfectly matched to the number system. They identified a precise threshold: if the computer word has three extra bits of space beyond what is strictly needed to hold the number, the centered format becomes strictly worse than the unsigned format. In fact, for the specific numbers used in current global encryption standards, the centered format leaks so much more information that an attacker would need far fewer observations to succeed. The study confirms this with real-world tests, including simulations and analysis of actual physical measurements from devices, showing that the theoretical weakness translates directly into practical vulnerability.

The paper also explores whether there is a perfect way to store these numbers to hide all leakage. The researchers found that the only way to completely eliminate the signal is to use a special code where every number is stored with the exact same number of "on" switches. While this is theoretically possible, it requires a much larger storage space than is practical for current systems. For the standard sizes used in real-world applications, such a perfect code does not exist. Instead, the study provides a clear law describing exactly how the leakage behaves, showing that the centered format creates a predictable pattern of errors that an attacker can use. This pattern is so distinct that it allows for a separation between the two storage methods that is mathematically guaranteed, regardless of the noise level.

The implications of these findings are immediate for the design of secure software. The study shows that the common practice of using centered representations for negative numbers in lattice-based cryptography is not neutral; it actively harms security. The author provides exact formulas that engineers can use to calculate the risk for any specific system configuration. They also offer a new method for testing security that is far more efficient than previous techniques, capable of analyzing complex systems in a fraction of the time. By proving that the centered format is not leakage-neutral, the research forces a reevaluation of how these critical encryption systems are built. It suggests that to achieve the highest level of security, developers should avoid the centered format in favor of the unsigned alternative, or at least be acutely aware of the specific vulnerabilities it introduces. The work stands as a rigorous, complete analysis that turns a vague concern about "representation" into a precise, actionable understanding of digital risk.

Technical Summary: Centered Arithmetic Is Not Leakage-Neutral

Problem Statement

In software implementations of lattice-based cryptography (e.g., ML-KEM, ML-DSA), sensitive values are protected via arithmetic masking, where a secret is split into random shares summing to the secret modulo $q$ . While the mathematical operation is modular, the physical storage of these shares requires a choice of representation within the machine word. Typically, shares are stored either as unsigned residues in $[0, q)$ or as centered signed integers in two's-complement form $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$ .

Although both encodings implement identical modular arithmetic, they differ significantly in their binary representation. Specifically, negative integers in two's-complement exhibit sign extension (leading ones), whereas their unsigned counterparts do not. Previous work has exploited this "sign extension" effect for side-channel attacks (e.g., absolute-value predictors). However, a comprehensive theoretical framework characterizing how this representation choice affects leakage across all orders of masking, under finite noise, and for arbitrary moduli has been lacking. This paper addresses the fundamental question: Is centered arithmetic leakage-neutral compared to unsigned storage?

Methodology

The paper employs a rigorous mathematical approach combining probability theory, Fourier analysis, and combinatorial number theory to model the side-channel leakage channel.

Finite-Noise Channel Modeling: The author models the leakage of masked shares as independent additive noise channels. They derive the exact likelihood of the masked sum by treating the problem as a cyclic convolution of the individual share leakage distributions.
Fourier Analysis: The analysis utilizes the Discrete Fourier Transform (DFT) to convert the convolution into a product in the frequency domain. This allows for the derivation of optimal attacks and the spectral decomposition of leakage.
Representation Minimax: The study evaluates different "sections" (representations) of $\mathbb{Z}_q$ by minimizing the energy of the leakage spectrum. This involves comparing contiguous sections (unsigned vs. centered) and arbitrary injective binary codebooks.
Spectral Decomposition: A key methodological innovation is the decomposition of the centered two's-complement leakage spectrum into sign-extension terms and carry terms, allowing for precise asymptotic analysis.
Algorithmic Validation: The theoretical bounds are verified through exact computations, synthetic experiments with full-size ML-KEM and ML-DSA parameters, and analysis of public physical traces.

Key Contributions

1. Optimal Finite-Noise Inference

The paper establishes that the complete likelihood of a masked sum can be computed in quasi-linear time $O(dq \log q)$ using a circular convolution evaluated via Fast Fourier Transform (FFT).

Result: This provides an optimal attack strategy that evaluates all $q$ hypotheses simultaneously.
Sufficiency Condition: The author derives an exact condition under which the commonly used product statistic (multiplying centered shares) retains all likelihood information. They prove that for non-negative leakage tables with a unique zero, the product statistic is strictly insufficient for any modulus $q \ge 2$ and order $d \ge 2$ under finite noise. The full observation contains strictly more information (higher KL divergence, Rényi divergence, etc.) than the product statistic.

2. Global Representation Minimax Laws

The paper optimizes the choice of representation to minimize leakage:

First-Order Leakage: Among all contiguous sections, unsigned storage ( $[0, q)$ ) is the unique minimizer of first-order leakage, unless the modulus $q$ occupies the full machine word ( $q=2^m$ ), in which case all sections are equivalent.
Higher-Order Leakage: The optimality of unsigned storage is not permanent. The paper identifies an exact "phase change" where, for specific parameters (e.g., $q=14, \beta=4$ ), centered storage becomes the unique minimizer for orders $d \ge 4$ , whereas unsigned is optimal for lower orders.
Lexicographic Law: For any finite family of representations, the eventual minimizer as the masking order $d \to \infty$ is determined by the lexicographically smallest sorted spectrum of leakage coefficients.
Constant-Weight Codebooks: For arbitrary binary encodings, leakage vanishes exactly if and only if the codebook has constant Hamming weight. The paper provides a sharp capacity bound for the existence of such codebooks ( $q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$ ) and calculates the minimum word width required for standard NIST moduli (e.g., $\beta=14$ for $q=3329$ ).

3. The Centered-Reduction Leakage Law

The paper's central theoretical result is an exact spectral decomposition of centered two's-complement leakage:

Decomposition: The leakage spectrum is split into a macroscopic sign-extension term and a binary carry defect.
Dominance Threshold: The paper proves a sharp uniform threshold: three excess bits ( $s = \beta - \lceil \log_2 q \rceil \ge 3$ ) are required for centered storage to exhibit a leakage magnitude strictly larger than unsigned storage at the first Fourier mode. Specifically, the condition $D(q, \beta) > 2U(q)$ holds if and only if $s \ge 3$ .
Asymptotics: For fixed excess width, the ratio of centered to unsigned leakage coefficients converges to $s+1$ . For the specific case of $q=2^m-1$ , the leakage ratio converges to a constant related to the sum of tangents ( $\kappa \approx 1.81$ ).
Neutrality: Centered arithmetic is not leakage-neutral. It is only neutral (leakage-equivalent to unsigned) in the exact case where $q=2^m$ and $\beta=m$ . In all other cases, centered storage results in strictly higher leakage at the first Fourier mode (and typically for low masking orders), though it may become the optimal representation at higher orders for specific parameter sets.

4. Robustness and Sample Complexity

Robustness Radii: The paper defines exact robustness radii for weighted Hamming-weight models, showing that the strict separation between centered and unsigned storage holds even with bit-sensitivity variations, provided the excess width is at least 3.
Sample Complexity: An exponential-confidence harmonic test is proposed. The paper proves that the sample complexity ratio between centered and unsigned attacks scales as the $2d$ -th power of the ratio of their spectral coefficients. This implies that for higher masking orders, the penalty for using centered storage (which has higher leakage at the first mode) grows exponentially, unless the specific parameter set places the system in a regime where centered storage is the global minimizer.

Results and Validation

Synthetic Experiments: Full-size implementations for ML-KEM ( $q=3329$ ) and ML-DSA ( $q=8380417$ ) confirm the theoretical sample complexity factors. For $d=3, 4, 6$ , the centered representation requires significantly more traces than unsigned storage to achieve the same success rate, aligning with the derived asymptotic limits.
Physical Traces: The analysis was validated against public physical traces from a masked ML-DSA implementation. The sign predicate achieved a Welch $|t|$ of 155.73 and 90.80% balanced accuracy, confirming the presence of the sign-extension leakage channel predicted by the theory.
Algorithmic Efficiency: The proposed optimal attack (using FFT-based convolution) successfully scored all hypotheses for $q=8,380,417$ in under 35 seconds, demonstrating practical feasibility.

Significance

The paper fundamentally shifts the understanding of arithmetic masking in software. It demonstrates that the choice of machine representation (centered vs. unsigned) is not merely an implementation detail but a critical component of the side-channel leakage channel.

Refutation of Neutrality: The author conclusively shows that "Centered Arithmetic Is Not Leakage-Neutral." The sign extension inherent in two's-complement representation introduces a distinct leakage spectrum that is not mitigated by masking alone.
Design Guidelines: The work provides exact, actionable guidelines for implementers:
- Use unsigned storage for first-order security and when excess bits are low ( $s < 3$ ), as it uniquely minimizes first-order leakage.
- Be aware that centered storage generally incurs a severe penalty in sample complexity due to higher leakage magnitude at the first mode, becoming optimal only at very high orders for specific parameter sets (demonstrating a phase change in optimality).
- Constant-weight codebooks offer a theoretical path to zero leakage but require specific word widths that may not align with standard hardware constraints.
Theoretical Foundation: By providing exact spectral laws and finite-noise optimality conditions, the paper closes the gap between theoretical masking security and practical implementation realities, offering a rigorous basis for evaluating and designing side-channel resistant lattice cryptosystems.