Speaker: Sergey Gorbunov
Department of Computer, University of Toronto
Title: Predicate Encryption for Circuits
In a predicate encryption scheme, a ciphertext is associated with an L-bit public index PIND (in addition to a message), and a secret key is associated with a predicate P. The secret key can decrypt the ciphertext iff P(PIND) = 1. Moreover, the scheme should be secure against collusions of users. That is, given secret keys for polynomially many predicates, an adversary learns nothing about the message if none of the secret keys can individually decrypt the ciphertext.
We present predicate encryption schemes for circuits of any arbitrary polynomial size, where the public parameters and ciphertext grow linearly with the depth of the circuit. Our construction is secure under the standard learning with errors (LWE) assumption. Previous constructions of predicate encryption were for Boolean formulas, captured by the complexity class NC1. In the course of our construction, we present a new framework for constructing predicate encryption schemes. In addition, our techniques lead the first construction of (weakly) reusable Yao's garbled circuits.
Joint work with Vinod Vaikuntanathan and Hoeteck Wee.