Skip to content

GGH Trapdoor

Goldreich–Goldwasser–Halevi · CRYPTO 1997 · lattice trapdoor

Builds one lattice with two bases, runs the same Babai round-off with each so you can watch the short one decrypt and the long one fail, then runs both historic attacks — Nguyen’s mod-6 reduction and the Nguyen–Regev fourth-moment descent — against the real decryptor and the real verifier.

What is a lattice trapdoor?

A lattice is every point you can reach by whole-number steps along a few fixed directions, and those directions are a basis. The same set of points can be described by a short, nearly square basis or by a long, badly skewed one — and the short one is the private key. That is the whole trick.

How that becomes encryption

Encrypting means stepping to a lattice point and then nudging slightly off it. To decrypt you must work out which point you started from. The arithmetic is the same either way — round to the nearest multiple of each basis vector — but with the short basis it lands on the right point and with the long one it does not. Nothing is hidden in that gap; the shape of the basis is the entire secret.

Not production cryptography. Real matrices, real reduction, real attacks, at dimensions 8–60. GGH is broken at every dimension — that is the subject, not a caveat.

Parameters

Every matrix on this page is this size. Break 2 needs at least 8 to be legible.

Everything on this page is reproducible from this seed.

Act 1 Two bases, one lattice

The private basis R is k·I plus small noise, so it is almost square. The public basis B = U·R for a random unimodular U. Same lattice, and the proof is exact integer arithmetic — no determinant is ever formed, because det B reaches 1089 here.

Same lattice, proved

Shape of each basis

The public basis, two ways

B = U·R is one of infinitely many bases of this lattice, and it carries traces of how it was built. Micciancio's fix is to publish the canonical one instead: every lattice has exactly one basis in Hermite normal form, so it cannot leak anything about the private basis it came from.

Both bases, projected to two dimensions

Real points of the lattice, with both bases drawn over them at one shared scale. Warm is the private basis, neutral the public one; each arrow is one basis vector.

Act 2 Encrypt, then decrypt twice

c = m·B + e. Decryption is Babai round-off: round(c·R−1)·R. The same three lines run with either basis. One number decides whether they work.

This is the toggle that decides whether Break 1 works at all. Changing it re-runs Acts 2 and 3; it does not touch Act 4.

Ciphertext

The decryption bound

Result: the same algorithm, twice

Encrypt a message, then decrypt it with each basis.

Baseline What ordinary reduction already does

Before either historical attack, the honest baseline: hand LLL nothing but the public basis and see what it gives back. At these dimensions the answer is uncomfortable, and the lab would be overclaiming if it did not show you.

Act 3 Break 1 — Nguyen 1999

Every entry of e is +3 or −3, and both are congruent to 3 modulo 6. So e + s ≡ 0 (mod 6) for s = (3,…,3), which means c + s ≡ m·B (mod 6) and the message’s residue falls out by linear algebra. The attack never touches the private basis.

    Result

    Step through the attack. It uses only the public basis and the ciphertext.

    Act 4 Break 2 — Nguyen–Regev 2006

    A different scheme: GGH signatures. Signing is round-off with R, so every signature leaks a point drawn uniformly from the parallelepiped spanned by the secret basis. Collect enough of them and the shape of that box gives up its edges.

    The signature cloud

    Each dot is one signature’s offset s − h, projected to two dimensions. Round-off signing fills the actual parallelepiped, corners and all.

    Signatures consumed

    Result

    Act 5 Why modern schemes look different