Power and Electromagnetic Attacks on the NTT and the Sampler

Abstract

For an attacker with physical access, the two operations that process the most secret material — the number-theoretic transform and the noise sampler — are the prime targets, and this piece examines how power and electromagnetic analysis exploits them. It introduces correlation power analysis, which recovers secret intermediates by collecting many traces and correlating leakage against a hypothesized value under a leakage model. It then explains why post-quantum schemes are uniquely exposed to single-trace attacks: because the transform's structure is fully known and its intermediates strongly constrain the secret, soft-analytical and belief-propagation techniques can recover a secret from a single trace, defeating the ephemeral-key defense that thwarts averaging attacks. It covers the sampler leak, where rejection counts and coefficient Hamming weights betray the secret noise or key, and why the transform's fixed arithmetic graph makes it so attackable. It closes by previewing masking and the agent-hardware exposure. The theme: physical leakage concentrates at the transform and the sampler, and single-trace attacks make even one-time use unsafe there.

When an attacker can measure a device's power draw or electromagnetic emanations, the question becomes where in the computation the secret is most exposed, and for a lattice scheme the answer is unambiguous: the number-theoretic transform and the noise sampler. The transform grinds through every secret coefficient in a fixed, publicly known pattern of arithmetic; the sampler manufactures the secret noise and key from randomness. Both radiate signals that correlate with the secret, and post-quantum schemes turn out to be uniquely vulnerable to single-trace attacks that recover the secret from just one execution — defeating the ephemeral-key hygiene that stops classical averaging attacks. This article examines those physical attacks on the two richest targets.

Correlation power analysis

The foundational physical attack is correlation power analysis. It rests on a leakage model: the power a device draws, or the field it radiates, at a given instant is approximately a function of the data being processed then — commonly the number of set bits, the Hamming weight, of an intermediate value — plus noise. An attacker collects many traces while the device operates on varying known inputs, forms a hypothesis about a small piece of the secret, predicts the intermediate value each input would produce under that hypothesis, and correlates the predicted leakage against the measured traces across all of them.

The hypothesis that correlates well is the correct one. For a wrong guess about a secret coefficient the predicted and measured leakage are uncorrelated noise; for the right guess they line up at the instant the device processes that intermediate, producing a correlation peak. By repeating this for each small piece of the secret, the attacker reconstructs it piece by piece. The attack's power comes from averaging: enough traces suppress the noise and make even a faint data-dependent signal detectable.

This averaging is also the classical attack's weakness, and the classical defense against it is to avoid reusing a secret so that the attacker cannot collect many traces of the same secret being processed. Ephemeral keys and fresh nonces deny the repetition that correlation power analysis needs. For post-quantum schemes, unfortunately, that defense is not sufficient, because of the single-trace attacks the next section describes.

Collect many traces on varying inputs, predict a secret-dependent intermediate under a leakage model, and correlate to recover each piece of the secret.

\[L = \mathrm{HW}(\text{intermediate}) + \text{noise}; \quad \text{correct hypothesis maximizes } \rho(L_{\text{pred}}, \text{power})\]

\[\text{more traces} \Rightarrow \text{noise averages down, signal emerges}\]

Single-trace attacks and why post-quantum is exposed

A single-trace attack recovers the secret from one execution, needing no repetition. It works when a single trace carries enough information — because the operation is very leaky, processes the secret across many measurable points, or has a structure that lets noisy leakage from many intermediates be combined. Post-quantum lattice schemes have exactly this character: the transform touches every secret coefficient at many points in one execution, and the sampler processes each secret value distinctly, so one trace contains a great deal of secret-correlated signal.

This is the crucial asymmetry with classical cryptography. The classical defense of never reusing a secret assumes the attacker must average across executions; a single-trace attack needs only one, so ephemeral keys and fresh randomness do not protect against it. A signing operation that uses a fresh nonce, or a key-generation that samples a key once, is fully exposed to a single-trace attack even though it would be safe against correlation power analysis. For physically accessible post-quantum devices, single-use is not a defense.

The techniques that make single-trace attacks succeed on these schemes are soft-analytical: rather than deciding each intermediate independently, they treat the whole computation as a graph of related values, extract noisy probabilistic information about each from the trace, and propagate those soft constraints through the known structure to converge on the secret. The transform's fixed arithmetic graph is what makes this so effective, as the next section explains.

Correlation analysis needs many traces and is thwarted by ephemeral keys; a single-trace attack needs one execution and defeats single-use.

The transform and the sampler as targets

The number-theoretic transform is a soft-analytical attacker's dream because its structure is a fixed, publicly known graph of butterfly operations, each combining two values with known constants. An attacker who extracts noisy leakage about the many intermediate values in this graph can use belief propagation over the graph to reconcile all the noisy observations into a consistent, high-confidence estimate of the input — the secret polynomial. The very regularity that makes the transform fast makes it attackable: the attacker knows exactly how every intermediate relates to the secret, so even weak per-intermediate leakage adds up to a strong recovery.

The noise sampler is the other rich target, and it leaks in scheme-specific ways. A rejection-based sampler betrays information through the number of rejections it performs, which is secret-correlated. Any sampler leaks through the Hamming weight or exact value of each coefficient it produces, and since it is producing the secret key or error directly, a single trace of the sampler can reveal those secret values. Sampling the secret key polynomial during key generation is therefore a prime single-trace target — the secret is being born in the clear of the power trace.

Both targets share the property that the attacker knows precisely what the operation is computing and how it relates to the secret, which is what turns physical leakage into recovery. This is why physical countermeasures focus on breaking that relationship — making the intermediate values processed by the transform and sampler independent of the secret through masking, or randomizing their order through shuffling, so that leaked observations no longer map cleanly onto secret coefficients.

The transform's known graph lets belief propagation combine weak leakage, and the sampler produces the secret directly, making both prime single-trace targets.

What this means for countermeasures

Because these attacks exploit a known relationship between processed intermediates and the secret, defending them means severing that relationship, which is qualitatively harder than the constant-time discipline that defeats timing attacks. Constant-time execution removes the timing channel but does nothing to hide the data-dependent power and electromagnetic signal; a perfectly constant-time transform still radiates the Hamming weights of its secret intermediates. Physical attacks therefore require physical countermeasures, chiefly masking — splitting each secret value into random shares processed separately so no single measured quantity depends on the secret — and shuffling the order of independent operations so leakage cannot be aligned to specific coefficients.

These countermeasures are the subject of the next article, and they are expensive: masking multiplies the cost of the protected operations and must be applied carefully throughout the transform and sampler to avoid leaving an unmasked intermediate. The important point here is that they are only warranted when the threat model includes a physically present attacker. A server in a data center is not the target of power analysis; a smart card, a secure element, or an edge device an adversary can hold is, and for those the masking cost is the price of security.

For autonomous AI systems the exposure is specific to the hardware. Confidential-inference enclaves and edge agents that run cryptographic operations on devices an adversary can physically access — a deployed sensor, an on-premises appliance, a hardware security module in an untrusted location — face exactly these power and electromagnetic single-trace attacks on their key generation, signing, and decapsulation. For such devices the guidance is to require masked, shuffled implementations validated against physical analysis, and to recognize that ephemeral keys and fresh nonces, while good practice, do not by themselves defend against single-trace recovery. The cloud-hosted agent faces timing; the physically deployed agent faces the transform and sampler under the probe.

⚠️

Ephemeral keys do not stop single-trace. Fresh keys and nonces defeat averaging attacks but not single-trace power or electromagnetic analysis of the transform and sampler, which recover the secret from one execution. Physically exposed devices need masking, not just single-use.

Key takeaways

For a physically present attacker, the number-theoretic transform and the noise sampler are the richest targets, because they process the most secret material in known patterns.
Correlation power analysis recovers secret pieces by collecting many traces and correlating measured leakage against a hypothesized intermediate under a leakage model such as Hamming weight; its power comes from averaging.
The classical defense of never reusing a secret denies the averaging correlation analysis needs — but single-trace attacks recover the secret from one execution, so ephemeral keys do not defend against them.
Post-quantum schemes are uniquely exposed to single-trace attacks because the transform's known arithmetic graph lets soft-analytical belief propagation combine weak per-intermediate leakage into a strong recovery.
The sampler leaks through rejection counts and coefficient Hamming weights, and since it produces the secret key or error directly, a single trace of key-generation sampling can reveal the secret.
Constant-time does not stop these physical attacks; masking and shuffling do, but at real cost, and are warranted only for physically exposed devices like inference enclaves, edge agents, and hardware modules in untrusted locations.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Assessing physical-attack exposurechecklist

Judge whether power and electromagnetic attacks are in scope.

Can an attacker physically access the device to measure power or emanation?
Does the implementation mask the transform and sampler, not just run constant-time?
Is key-generation sampling protected against single-trace recovery?
Is operation order shuffled to prevent aligning leakage to coefficients?
Is the implementation validated against physical side-channel analysis?

🚀Harden a physically exposed devicequickstart

Defend the transform and sampler on hardware an adversary can hold.

Adopt a masked, shuffled implementation, not only a constant-time one.
Protect the sampler and key generation as single-trace targets.
Do not rely on ephemeral keys alone against single-trace attacks.
Validate against power and electromagnetic analysis on the target hardware.

🔒Physical-countermeasure policypolicy

A stub scoping physical defenses to exposed hardware.

physical_side_channel:
  applies_when: attacker_has_device_access
  transform: masked_and_shuffled
  sampler: masked_single_trace_hardened
  key_generation: protected
  constant_time_alone: insufficient
ephemeral_keys:
  defends_averaging: true
  defends_single_trace: false

Illustrative documentation template, not a product config.

Glossary

Correlation power analysis: Recovering secret pieces by correlating measured power or electromagnetic leakage across many traces against a hypothesized intermediate under a leakage model.
Leakage model: An approximation (often Hamming weight) of how a device's power or emanation depends on the data it processes, used to predict leakage for a key hypothesis.
Single-trace attack: Recovering the secret from a single execution, needing no repetition, and therefore defeating the ephemeral-key defense against averaging.
Soft-analytical / belief propagation: Combining noisy probabilistic leakage about many related intermediates by propagating constraints through a known computation graph to recover the secret.
Sampler leak: Secret information betrayed by the noise sampler through rejection counts or the Hamming weights and values of the secret coefficients it produces.
Masking / shuffling: Physical countermeasures: splitting secrets into random shares processed separately, and randomizing operation order, to break the leakage-to-secret relationship.