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.
- Who's exposed: sparse-secret FHE / bootstrapping deployments with a side-channel leakage path.
- Safer pattern: raise the Hamming weight h, mask / rate-limit leakage, and treat hint-availability as part of the threat model.
- What this is: an estimator of hint counts — it runs no attack, no lattice reduction, no randomness.
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
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.
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
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 ~h·log₂h such equations and the h unknowns are
pinned down. That is the whole game — and why the budget scales with
h, not n.
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).
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:
-
Power analysis (DPA / CPA). Each multiply-accumulate over
sdraws a secret-dependent amount of power. Averaging many traces of the same operation recovers coordinate-level information — a classic source of inner-product hints. - Cache & timing. Secret-dependent table lookups or branches in NTT / key-switch code leave a cache-access or timing footprint an on-host or co-resident attacker can read.
- EM emanation. A near-field probe over the chip captures the same secret-dependent switching as power analysis, often without physical contact.
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:
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.
| Regime | n | h | Prior hints | New hints | Validated hints | Source |
|---|
Verify it yourself
Known gaps (honest by construction)
-
This is a fit, not a re-run. The model is an idealized
C·h·log₂hcurve (C = 2), not a re-execution of the paper's lattice estimator. It reproduces every row of the paper's Table 1 exactly (h = 32, 64, 128, 192 → 320, 768, 1792, 2913), but is not claimed to extrapolate arbitrarily beyond those regimes. - The GAA is an assumption. The O(h log h) law is empirical / heuristic under the Gaussian Approximation Assumption — a conservative lower-bound analysis, not a worst-case proof.
-
Hint type varies by regime. The "Validated hints"
column above transcribes what the paper actually tested per row — e.g.
the OpenFHE
(2¹⁵, 192)regime is perfect hints only (approximate not yet validated there), while the(2¹⁵, 32)anchor covers approximate + perfect. -
q is not modeled. Table 1 lists a modulus bit-size
log₂ qper row (recorded inPAPER-NOTES.md); the hint-count laws don't depend on the modulus, so the demo keys off(n, h)only. - Hints presuppose a leakage channel this demo does not model. "Recoverable" means the hint budget is met — not that an attack was run.