LWE ⇒ Selectively secure HIBE (bonsai trees)

Fully-black-box reduction · standard model · CHKP10, ABB10 · security loss: tight up to a factor 2: one run of the adversary, its challenge ciphertext built from the LWE samples, whose advantage is at most twice the LWE advantage plus statistical terms from the leftover hash lemma and trapdoor sampling

Statement

If LWE is hard with polynomial modulus-to-noise ratio, there is a selectively secure HIBE scheme of every constant depth $d$ in the standard model: depth $d$ uses modulus and inverse error rate $n^{O(d)}$, since each level of delegation multiplies the Gaussian parameter by a $\mathrm{poly}(n)$ factor — CHKP10, ABB10.

Sketch

A short basis of ${\Lambda }_q^{\perp }(\mathbf{A})$ yields a short basis of ${\Lambda }_q^{\perp }([\mathbf{A}\mid {\mathbf{A}}^{\prime }])$ for any ${\mathbf{A}}^{\prime }$, without revealing the original basis, so a key for an identity delegates keys to its descendants. In CHKP10 the matrix for an identity concatenates one public block per identity bit; in ABB10 each level contributes one block ${\mathbf{A}}_i+H({id}_i)\mathbf{B}$ for an injective encoding $H$ with invertible differences. The reduction sets up the blocks so that it knows trapdoors for every identity except the committed challenge identity, whose matrix carries its LWE samples — CHKP10, ABB10.

Notes

• Efficiency: the lattice dimension grows linearly with the total identity length in CHKP10 and with the depth alone in ABB10 — ABB10.
• A HIBE of depth one is an IBE: HIBE ⇒ IBE. In the random-oracle model a simpler IBE is the GPV scheme — GPV08.