Skip to content

LWE Hints

sparse-ternary LWE · ePrint 2026/1081

Estimate how many side-channel hints recover a sparse-ternary LWE secret, comparing the new O(h·log₂h) hint budget against the prior ≈n/2 baseline across the paper's (n, h) regimes.

TL;DR

Sparse LWE secrets leak cheaply. Older attacks needed about n/2 side-channel hints; this paper shows you need only about h·log₂h. For an FHE bootstrapping regime (n = 2¹⁵, h = 32) that is 320 hints instead of 16,384 — a ~50× drop.

Visualizing one result of Hhan et al., “From Perfect to Approximate Hints”, IACR ePrint 2026/1081. The counts come from the paper’s heuristic analysis under the Gaussian Approximation Assumption — not from running an attack.

Live readout

Dimension n —
Hamming weight h —
Hints — this method heuristic · GAA —
Hints — prior work baseline —
Reduction factor —

This means the paper's hint budget is met — it does not mean this page ran an attack.

Interactive chart

Hints needed vs Hamming weight h (log-scaled x-axis). Every modeled point is heuristic · GAA-based.

Drag h → the dot on the solid (new) curve moves. Drag n → only the dashed (prior) line moves. The old threshold cares about n; the new one mostly cares about h.

Why is the prior baseline n/2? Prior work treated s as a generic n-dimensional secret and ignored its sparsity, so it needed roughly one hint per two coordinates — n/2 — no matter how few were actually nonzero. This paper's advance is refusing to pay for the zeros: it charges only for the h nonzeros (and the log cost of locating them). That is why the gap between the two lines is the headline — it is exactly what sparsity buys back.

Solid: this method C·h·log₂h. Dashed: prior baseline n/2 for the selected n. ◆ = the four paper Table 1 weights h = 32, 64, 128, 192 — click one to load that regime.

How it works

New to LWE? Start here — what is the attacker even holding?

LWE (Learning With Errors) is the hard problem under lattice crypto and FHE. The attacker already has a big pile of noisy linear equations in the secret:

A·s + e = b

Here A and b are known (many rows of them), s is the secret vector they want, and e is small random noise added to every equation. Without the noise this is just linear algebra — you would solve for s in a heartbeat. The noise e is exactly what makes LWE hard: it smears every equation just enough that no efficient solver is known.

A side-channel hint is an extra, cleaner equation about s that leaks out of the hardware — not from the math, but from power draw, timing, or EM while the device computes with s. Each hint is one more constraint, and (unlike the LWE rows) it can be noise-free or only lightly noisy. The whole question of this demo is: how many such hints does it take to finish off s?

An LWE secret here is a sparse ternary vector s ∈ {−1, 0, +1}ⁿ with only h nonzero entries (h ≪ n). A side channel can leak hints — linear equations about s:

—

Perfect hint

l = ⟨v, s⟩

An exact inner product. Maximally informative.

Approximate hint

l = ⟨v, s⟩ + e

A noisy inner product (e small). Realistic leakage is usually like this.

What one hint actually gives the attacker

A hint is one linear equation on the secret. The attacker picks a known probe vector v; the side channel leaks its inner product with s. Only the h nonzero coordinates of s contribute a term — so each equation really constrains just those h unknowns.

Stack enough such equations and the h unknowns get pinned down. But how many is “enough”? Not just h — it is h·log₂h, and that extra log₂h is the whole surprise. The next panel shows where it hides: the attacker must also find which coordinates are nonzero.

The surprise: the leakage doesn't have to be clean. Even approximate (noisy) hints — the right tab above — still yield O(h·log₂h)-scale recovery in the paper's validated regimes — so imperfect side-channel data can be enough.

Why sparsity is the lever: the attacker doesn't need to pin down all n coordinates — only the h nonzero ones. The work scales with the information content of the secret (≈ h·log₂h), not its ambient dimension n. When h ≪ n, O(h log h) crushes O(n).

Why h·log₂h, not just h?

Here is the puzzle. There are h unknown nonzero values, so h equations should pin them down — that would be O(h). Yet the law is O(h·log₂h). Where does the extra log₂h come from? From not knowing which coordinates are the nonzero ones. Finding a value is cheap; finding its position is a search.

Below is a tiny secret: h = 3 nonzeros hidden among n = 16 coordinates. Add locating hints one at a time. Each locating hint answers a single yes/no question — “does a nonzero lie in this half?” — and rules out half the remaining candidates. Watch the ambiguous cells (positions that could still be a nonzero) shrink. Only when a cell is the last one standing is its position pinned down.

That is the log₂h. Isolating one nonzero position takes about log₂(window) yes/no hints — a binary search — and you must do it for each of the h nonzeros. So the total is not h but ≈ h·log₂h: h for the values, times a log factor to locate them. (Real recovery interleaves value and position information rather than separating them this cleanly — this is the intuition, not the exact protocol — but the log factor is genuinely the cost of position-finding: a coupon-collector / group-testing overhead.)

Where hints come from in practice

This page assumes a leakage channel; it does not model one. But the assumption is realistic. On real FHE implementations, a hint — one linear equation on the secret — can fall out of physical side channels during the secret-dependent steps of bootstrapping, key-switching, or the NTT:

Each captured trace yields one or more hints — often approximate (noisy) ones. The calculator below turns a per-operation leak rate into an accumulated hint count and a Safe / Manageable / Dangerous verdict for the selected (n, h).

Threat-scenario calculator

Estimate whether your deployment leaks enough hints to cross the new-method threshold for the selected (n, h). Outputs are heuristic · GAA-based.

Start from an illustrative scenario, then tune the numbers:

The leak rate is not from the paper — it depends entirely on your hardware and countermeasures (see Where hints come from). It is the knob a defender actually controls: masking, shuffling, and rate-limiting all push it toward zero. The scenario buttons above set it to plausible values so the verdict tracks a real deployment, not an arbitrary number.

—

Quick self-check

If n doubles (say 2¹⁵ → 2¹⁶) but the Hamming weight h stays 32, what happens to this method's hint threshold?

Misconceptions

Does this break Kyber / Dilithium?

No. ML-KEM (Kyber) and ML-DSA (Dilithium) use non-sparse secrets. This result leverages the sparse ternary structure common in FHE schemes. The lever here is low Hamming weight — remove the sparsity and the speedup is gone.

Is LWE broken?

No. This is secret recovery given side-channel hints. With no hints there is no speedup — per-instance LWE hardness without leakage is intact. The contribution is that fewer hints than previously thought are enough.

Is O(h log h) proven?

No — it is empirical / heuristic under the GAA (Gaussian Approximation Assumption), a conservative lower-bound analysis validated on FHE parameter sets. It is not a worst-case proof.

Does this demo run the attack?

No. It computes hint counts with plain arithmetic (C·h·log₂h vs n/2). No lattice reduction, no side channel, no randomness, no network. Same input ⇒ same output.

Parameters & sources

Source of truth: Minki Hhan, Ga Hee Hong, Jiseung Kim, Changmin Lee, and JeongHwan Lee, "From Perfect to Approximate Hints", IACR ePrint 2026/1081. Full transcription with citations is in PAPER-NOTES.md.

Regimenh Prior hintsNew hints Validated hintsSource

Verify it yourself

Known gaps (honest by construction)