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 — the paper reports a heuristic O(h·log₂h) hint budget under the GAA. The next panel illustrates the separate task of finding which coordinates are nonzero, using a toy binary search whose log₂n cost does not derive that law.

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).

Finding positions: log₂n search cost

Knowing the h nonzero values does not tell you which of the n coordinates contain them. This interactive illustrates that extra search work with independent binary searches. It does not derive the paper's O(h·log₂h) heuristic.

Below are h = 3 nonzeros hidden among n = 16 coordinates. Each button press advances one search round: one separate yes/no locating hint per nonzero, asking whether that target lies in the lower half of its remaining window. The three searches advance together; a round uses three independent hints, not one shared hint. Watch the ambiguous cells shrink until each position is pinned down.

This toy search costs log₂n per nonzero. The worst case is ⌈log₂n⌉ hints per position, or h·⌈log₂n⌉ independent hints overall: here, 4 per position and 12 in total. Doubling n to 32 raises the per-position cost to 5. The separate recovery exhibit uses adaptive group testing and reports its own prediction h·⌈log₂(n/h)⌉ + h, including value hints. Neither cost is the paper's 2h·log₂h estimator; that estimator remains a separate, GAA-based fit to the paper's Table 1.

Run it: recover a real secret from real hints

Everything above this line estimates. This runs. The page generates a genuine LWE instance — A·s + e = b (mod q) with q = 3329, a sparse ternary s, errors in [−2, 2] — and then recovers s from perfect hints l = ⟨v, s⟩ mod q. The attack reads only the hints; the planted secret is used afterwards, to check the answer.

Toy parameters, stated plainly: n in the hundreds and a 12-bit modulus, not n = 2¹⁵ with a 700-bit one. And this is not a re-run of ePrint 2026/1081 — that method handles approximate hints, leans on the GAA, and finishes with lattice reduction, so its hint count is a different number from the one below and neither validates the other. What this does demonstrate, on a real instance rather than in prose, is the structure they share: locating which coordinates are nonzero is the expensive part, that search costs on the order of h·log₂(n/h), and the total therefore scales with h and the log of the dimension rather than with n.

1 · Instance
—
2 · Locating the support
—
3 · Solving for the values
—
4 · Total hints spent
—
5 · Recovered secret vs planted secret
—
6 · Does it explain the LWE samples?
—
7 · Control: a different sparse secret
—

—

The same recovery at a fixed dimension across Hamming weights. The measured cost climbs with h; the prior n/2 threshold does not move at all, because it never knew the secret was sparse.
h Support hints Value hints Total measured Per nonzero Prior n/2 Recovered?
Press “Sweep h” to run it.

The GAA, measured

Every modeled number on this page carries a heuristic · GAA badge, because the paper's law is empirical under the Gaussian Approximation Assumption. A badge tells you a claim is conditional; it never lets you see the condition. This does.

A perfect hint is l = ⟨v, s⟩. With a sparse ternary secret of weight h and a probe drawn uniformly from {−8, …, 8}ⁿ, l is a sum of exactly h independent symmetric terms — so the assumption makes a falsifiable prediction: mean 0 and standard deviation √(h · σ²) with σ² = 24. The page draws 4,000 hints and compares them against that Gaussian — not against one refitted to the sample, which would quietly hand the assumption its own parameters.

Bars: 4,000 sampled hint values. Curve: the Gaussian the GAA predicts from h alone.
Predicted spread √(h·σ²)
—
Measured spread
—
Kolmogorov–Smirnov D
—
5% critical value 1.36/√N
—

—

A KS test at α = 0.05 rejects a perfectly Gaussian sample one run in twenty, so a single rejection at large h is noise — change the seed and watch. What is not noise is h = 1 and h = 2, which are rejected on every seed by a wide margin. The assumption is a central-limit-theorem claim, and it gets weaker exactly where the secret gets sparser — which is the direction FHE parameter choices push.

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.

—

Or paste your own leakage profile

A flat rate times a count of operations is a convenient fiction. Real leakage has quiet stretches, bursts while a key is in use, and a step change the day someone turns masking on. Type or paste what your own campaign looks like — one number per period, newline- or comma-separated, with an optional label: prefix and # comments. The threshold it is measured against is C·h·log₂h for the (n, h) selected above, so moving the h slider moves the line your profile has to cross.

Anything that is not a non-negative number is reported against its line rather than quietly treated as zero.

Bars: hints leaked in each period. Line: the running total. Dashed: the C·h·log₂h threshold for the selected regime.
Periods parsed
—
Total hints
—
Threshold for this (n, h)
—
Largest single period
—

—

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?

Not the paper's attack. The estimator computes hint counts with plain arithmetic (C·h·log₂h vs n/2): no lattice reduction, no side channel, no network, and the same input gives the same output. Run it, further up, does perform a genuine secret recovery on a real LWE instance from a seeded generator — but with perfect hints at toy parameters, finishing in Gaussian elimination rather than lattice reduction, so its hint count is its own number.

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

Hint count and recovery cost are different

Having enough hints leaves a computational problem to solve. Yang, Cao, Yin and Cheng, Optimized Solving Strategy and Two-Step Estimator for LWE with Hints (preprint, published 14 November 2026) report secret recovery on a CRYSTALS-KYBER 512 instance using supplied perfect hints and a tuned combination of BKZ lattice reduction and sieving. A perfect hint is an exact relation; approximate hints include error.

Their experiment assumes the hints are available; it does not show how to obtain them from a deployed device or break ML-KEM without leakage. Its Kyber setting differs from the sparse-ternary FHE model above. This page neither runs their solver nor uses their timings to calibrate its calculator; its toy recovery uses linear algebra.

Verify it yourself

Known gaps (honest by construction)