LWE with sub-exponential ratio ⇒ Selectively secure ABE for circuits (GVW)

Fully-black-box reduction · standard model · GVW13 · security loss: tight up to a factor 2: one run of the ABE adversary, its challenge ciphertext built from the LWE samples, whose advantage is at most twice the LWE advantage plus statistical terms from the simulated keys

Statement

If LWE with sub-exponential modulus-to-noise ratio is hard, then for every depth $d$ fixed at setup there is a selectively secure key-policy ABE scheme for all circuits of depth $d$, whose public parameters and ciphertexts grow linearly in $d$ — GVW13.

Notes

• Earlier ABE schemes, from pairings, handle Boolean formulas, that is ${\mathbf{NC}}^1$ (BDH ⇒ ABE); GVW13’s handle arbitrary polynomial-size circuits of bounded depth — GVW13.
• Secret keys whose size grows with the circuit’s depth but not its size follow from the same assumption by key-homomorphic encryption — BGG+14.
• The noise grows by a factor polynomial in the dimension $n$ at each level of the circuit, so depth $d$ needs a modulus-to-noise ratio $n^{O(d)}=2^{O(d\log n)}$, at most $2^{n^{\epsilon }}$ once $n^{\epsilon }\ge cd\log n$ for a suitable constant $c$ — GVW13.