Predicate Encryption for Circuits from Standard Lattices
Sergey Gorbunov


In predicate encryption, a ciphertext is associated with descriptive attribute values $x$ in addition to a plaintext $\mu$, and a secret key is associated with a predicate $f$. Decryption returns plaintext $\mu$ if and only if $f(x) = 1$. Moreover, security of predicate encryption guarantees that an adversary learns nothing about the attribute $x$ or the plaintext $\mu$ from a ciphertext, given arbitrary many secret keys that are not authorized to decrypt the ciphertext individually.

We construct a leveled predicate encryption scheme for all circuits, assuming the hardness of the subexponential learning with errors problem. That is, for any polynomial function $d = d(\secp)$, we construct a predicate encryption scheme for the class of all circuits with depth bounded by $d(\secp)$, where $\secp$ is the security parameter.

Joint work with: Vinod Vaikuntanathan (MIT) and Hoeteck Wee (ENS)