Lattice trapdoors

A lattice trapdoor for a matrix is secret information, classically a short basis of the lattice , that can be generated together with a nearly uniform and lets its holder sample short preimages under and invert the LWE function — GPV08.

Definitions

For and , the -ary lattices and coset are

all modulo , and — standard. Finding a short nonzero vector of for uniform is the SIS problem, and decoding a point near is LWE. A trapdoor is a basis of whose vectors, or whose Gram–Schmidt vectors , are short; its quality is , the length of the longest Gram–Schmidt vector.

Generation

There is an efficient algorithm that outputs statistically close to uniform together with a short basis of — Ajt99. For with a suitable constant , the basis can have and — AP09.

Preimage sampling and inversion

Given a trapdoor , discrete Gaussian sampling over the coset at width (discrete Gaussians) outputs a short with , distributed, up to negligible statistical distance, as conditioned on , independently of . Since is nearly uniform for such when the columns of generate , sampling then is statistically close to sampling then : the map is a preimage sampleable function, collision-resistant under SIS — GPV08. The same trapdoor recovers from when is short enough relative to and , so LWE with a trapdoor is an injective trapdoor function — GPV08.

Preimage sampleable functions give hash-and-sign signatures, strongly unforgeable in the random-oracle model under SIS (SIS ⇒ DS), and the identity-based encryption of LWE ⇒ IBE (GPV), whose secret key for an identity is a short preimage of its hash — GPV08.

Gadget trapdoors

Let , and , the gadget matrix. Inverting LWE and sampling short preimages for is easy, essentially by binary decomposition, and has a known basis with — MP12. A -trapdoor for is a matrix with small entries such that for an invertible ; for instance for uniform and random short . With , sampling and inversion for reduce to those for , with quality governed by the largest singular value of , which gives simpler, tighter and faster trapdoor algorithms than short bases — MP12.

Delegation

A short basis of extends to a basis of of the same Gram–Schmidt quality for every , provided the columns of generate , and can be re-randomized, at a loss in quality for the new lattice dimension , so that the new basis reveals nothing about the old one; this delegation gives selectively secure hierarchical IBE of constant depth from LWE (LWE ⇒ selectively secure HIBE) — CHKP10.