LWE ⇒ IBE (Gentry–Peikert–Vaikuntanathan, random oracle model)

Fully-black-box reduction · random oracle model · GPV08 · security loss: a factor about the number of random-oracle queries, from guessing the challenge identity’s query

Statement

If LWE is hard with polynomial modulus-to-noise ratio, then in the random-oracle model there is an IND-ID-CPA-secure IBE scheme: the master public key is an $\mathbf{A}\in {\mathbb{Z}}_q^{n\times m}$, statistically close to uniform, generated with a short basis of ${\Lambda }_q^{\perp }(\mathbf{A})$, the key for an identity $id$ is a short $\mathbf{e}$ with $\mathbf{Ae}=H(id)\mathrm{mod}q$ sampled from a discrete Gaussian with that basis, and encryption is dual-Regev encryption under $(\mathbf{A},H(id))$ — GPV08.

Sketch

Preimage sampling makes the key $\mathbf{e}$ a discrete Gaussian conditioned on $\mathbf{Ae}=H(id)$, so the reduction can sample $\mathbf{e}$ first and program $H(id):=\mathbf{Ae}$, which is statistically close to uniform, for every identity except the guessed challenge identity, whose syndrome it takes from its LWE samples. Dual-Regev ciphertexts under that syndrome are then pseudorandom by LWE — GPV08.

Notes

• The scheme is anonymous: ciphertexts are pseudorandom, so they hide the identity as well as the message — GPV08.
• Standard-model lattice IBE and HIBE follow from basis delegation: LWE ⇒ selectively secure HIBE — CHKP10, ABB10.
• The same preimage-sampleable functions give hash-and-sign signatures: SIS ⇒ DS — GPV08.