NTRU Fundamentals — recovering the short (f,g) key pair via lattice reduction

NTRU is a lattice cryptosystem over the convolution ring R_q = Z_q[x]/(x^N - 1): the private key is a pair of *small* polynomials (f, g), the public key is the single polynomial h = g · f^{-1} mod q, and recovering (f, g) from h alone is exactly the short-vector problem the NTRU lattice is built to encode.

The signal that betrays it

- The public key is a single polynomial `h` — there's no modulus to factor and no discrete log to take; if you catch yourself reaching for RSA/DH tooling on a challenge whose only public artifact is one polynomial, stop and check for NTRU instead. - Explicit parameters (N, p, q) are named or inferable: q is a power of 2 (or another smallish, structured modulus), p is small — very often literally 3 — and p, q are coprime. - The private key or noise terms are described as ternary: coefficients restricted to {-1, 0, 1} (sometimes {-1,0,1} with a fixed count of each, i.e. a fixed-weight ternary polynomial). - The word "convolution" shows up in the challenge text or code (R_q = Z_q[x]/(x^N - 1) multiplication is polynomial convolution) — this is close to a dead giveaway. - Ciphertext has the shape e = r·h + m (or a close variant): a random small blinding polynomial r times the public key, plus the message. - Key generation sometimes fixes f ≡ 1 mod p as a convention — worth checking explicitly, because it simplifies (or hands you) f_p^{-1} during decryption. - The number that actually decides whether this attack is worth starting: `N`. CTF instances keep N small (order of tens to low hundreds) specifically so lattice reduction finishes in seconds to minutes. This is the single most important sanity check before writing any lattice code — see "What does NOT work" below for why it doesn't generalize past CTF-sized N.

How to exploit it

Recover (f, g) by lattice reduction on the classic Coppersmith–Shamir 2N × 2N NTRU lattice. Build the circulant matrix H of the public polynomial h (row i is h cyclically shifted by i), then reduce the block basis:

``python from sage.all import * H = Matrix(ZZ, N, N, lambda i, j: h_coeffs[(j - i) % N]) # circulant of h L = block_matrix([[identity_matrix(N), H], [zero_matrix(N), q * identity_matrix(N)]]) short = L.LLL()[0] f = short[:N] # candidate private f g = short[N:] # candidate private g ``

Operational detail from the field:

- LLL alone is enough at CTF scale. With small N this runs fast — you don't need to reach for BKZ unless plain LLL comes back empty (see below for when it stops being enough). - The reduced basis can hand back more than one usable row, and thanks to the circulant structure any cyclic rotation x^i·f, x^i·g of a valid key pair is *also* a valid short vector and *also* decrypts correctly (this rotation-equivalence is exactly what Coppersmith–Shamir's original paper means by finding "the original secret key, or an alternative secret key which is equally useful"). Don't assume the first short row you find is *the* literal (f, g) used at keygen — treat it as a candidate. - Always verify by test-decrypting, the same discipline as any lattice attack: take the candidate f, decrypt a known or self-checkable ciphertext, and confirm the plaintext comes out sane before trusting the recovered key. - Decryption once `(f, g)` (or an equivalent rotation) is in hand: compute a = f · e mod q, center-lift the coefficients into (-q/2, q/2] before doing anything else — this centering step is not optional, reducing into the wrong representative range silently produces garbage even when the (f,g) recovery itself was correct — then reduce a mod the small p, and multiply by f_p^{-1} (the inverse of f mod p, not mod q) to recover the message. - Partial-key leaks compose with this. If only some bits/coefficients of f are exposed (a side channel, a debug leak, a weakened keygen), that's a Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction / Partial Key Exposure — recovering RSA when part of p or d has leaked-flavored problem layered on top of the same NTRU lattice structure, not a reason to abandon lattice reduction — it usually makes the target vector easier to pin down, not harder. - This whole construction is a direct instance of "encode a bounded unknown as a short lattice vector" — see Lattice Fundamentals — encoding a bounded unknown as a short vector for the general framing and LLL Reduction — the polynomial-time workhorse behind almost every lattice attack for the reduction step doing the actual work.

What does NOT work

- Running plain LLL (or even LLL-then-a-little-BKZ) against production/NIST-scale NTRU parameters and expecting the same quick win. NIST's standardized NTRU parameter sets push N far past CTF territory — NTRU-HPS goes up to N = 1229 and NTRU-HRSS up to N = 1373, with correspondingly sized q; the lattice dimension is 2N (2400+ at the top end), and at that size the shortest vector no longer stands out enough for LLL to find directly — recovering the key needs BKZ with a large, carefully tuned block size, and even then success is far from guaranteed in any reasonable time budget. The field-tested recipe above is a CTF-scale technique; treat a large, realistic N as a sign this is not the intended path (or that you need heavier tooling than a quick Sage script). - Confusing this "just reduce harder" wall with the separate overstretched-parameter attack surface. Certain non-standard NTRU-derived schemes (some homomorphic-encryption and PIR constructions) pick q disproportionately large relative to N ("overstretched" parameters); those fall to a *different*, subfield-lattice attack that exploits the skewed q/N ratio specifically, not to "the same basis but with more BKZ." If the parameters look overstretched, that's a different rabbit hole, not an escalation of this one. - Assuming the raw recovered vector is unique or canonical. As noted above, cyclic rotations of (f, g) are equally short and equally valid; don't burn time trying to match a recovered candidate against an assumed "canonical" form before verifying it decrypts correctly — verification is the only check that matters. - Skipping the centered-lift step and blaming the lattice reduction when decryption comes out wrong. This is the most common self-inflicted dead end: the (f,g) recovery can be completely correct and decryption still fails if a = f·e mod q is reduced into [0, q) instead of centered (-q/2, q/2] before the mod-p step. - Brute-forcing `(f, g)` by direct coefficient search. The space of ternary polynomials of length N is 3^N — astronomically larger than anything lattice reduction needs to explore, and not rescued by "just try small N first" the way it might be for other small-parameter attacks.

Related

Lattice Fundamentals — encoding a bounded unknown as a short vector LLL Reduction — the polynomial-time workhorse behind almost every lattice attack Ring-LWE — recognizing polynomial-ring LWE and reducing it to plain LWE LWE Fundamentals — recognizing and breaking noisy linear equations mod q Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction Partial Key Exposure — recovering RSA when part of p or d has leaked