Luna Labs All projects
A3 · Lattice-attack lab

A3 · Lattice-attack lab

Where does a lattice attack stop working?

Small LWE instances put lattice-attack estimates to an experimental test.

Break points measured with fpylll; 2016 estimate computed in the browser; lattice estimator compared from a recorded run.

Measured against predicted
Lab inputs

Lab inputs

Parameter set

Prediction

01 / Experiment

Measured against predicted

Instance, broken by BKZ LLL alone Not recovered by the cap Median Equal values

Scatter chart. Left and right arrow keys move between instances of a set, up and down move between sets, Home and End select the first and last instance; Escape hides the reading.

The spread matters

Parameter grid and medians

02 / Success curve

How often each block size succeeds

Chart. Left and right arrow keys move along the tested block sizes; Home and End select the first and last; Escape hides the reading.

Recovered by the prediction

03 / Live demonstration

Watch LLL work

A separate small instance · independent of the measured grid

True secret

—

Recovered secret

—

Before After LLL GSA reference

Chart. Left and right arrow keys move along the basis index; Escape hides the reading.

04 / Runtime

What a larger block costs

Median BKZ call Observed range

Chart. Left and right arrow keys move along the timed block sizes; Home and End select the first and last; Escape hides the reading.

Timing data

05 / Scale

The same estimator on ML‑KEM

ML‑KEM-768 secret space

Attack dimension and cost model

06 / Attack

The attack in four steps

From noisy equations to a checked candidate secret

  1. 01

    b = As + e mod q

    Generate the instance

    Noisy equations hide a small secret behind modular arithmetic.

  2. 02

    Build the embedding

    The equations become a lattice containing a short target vector.

  3. 03

    Reduce the basis

    LLL runs first. BKZ searches larger blocks until the attack succeeds.

  4. 04

    short vector → candidate scheck every coordinate

    Check the secret

    The candidate is read from a short vector and compared with the known secret.

Flat schematic; not the experiment’s basis geometry. The method notes give the embedding and its scaling.

07 / Warm-up

Why the modulus matters

Without modular wrapping, least squares can recover the small secret by rounding. Wrapping changes the equations, so an ordinary real-valued fit can miss it.

08 / Method notes

What the experiment establishes

Assumptions, success criteria and repeatability

Sources and dates

    Read the full analysis Technical note (PDF) Notebook