NTRU + NTRU-SIS ⇒ DS

Random oracle model · DLP14 · security loss: tight up to statistical terms: the reduction programs every hash value as the image of a short vector it samples, so a forgery yields an SIS solution over the NTRU lattice without guessing

Statement

If NTRU and SIS over NTRU lattices are hard, the GPV08 hash-and-sign signature scheme, instantiated with an NTRU trapdoor $(f,g)$ for $h=g\cdot f^{-1}\mathrm{mod}q$, is EUF-CMA-unforgeable in the random-oracle model — DLP14. Falcon, the instantiation selected by NIST for standardization, samples preimages by fast Fourier sampling over the NTRU trapdoor and has $666$-byte signatures at Falcon-512 — FHK+20.

Sketch

The trapdoor is a short basis of the NTRU lattice $\{(s_1,s_2):s_1+s_{2}h=0\mathrm{mod}q\}$, with which the signer samples a short $(s_1,s_2)$ with $s_1+s_{2}h=H(m)$; verification checks this equation and the norm bound. The GPV reduction programs $H(m)$ as the image of a fresh short vector, so a forgery on $m$ is, except with negligible probability, a second short preimage of $H(m)$, and the difference of the two is a short nonzero vector in the NTRU lattice.

Notes

• Falcon’s security proof is also given in the quantum random-oracle model — FHK+20.