Paper 2016/654

Interpolating Predicate and Functional Encryption from Learning With Errors

Shweta Agrawal

Abstract

We construct a functional encryption scheme for circuits which achieves a notion of security that interpolates predicate and functional encryption. Our scheme is secure based on the subexponential learning with errors (LWE) assumption. Our construction simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions, namely the predicate encryption scheme of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) and the reusable garbled circuits scheme of Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013). Our contributions may be summarized as follows: 1. We show that existing LWE based predicate encryption schemes [AFV11, GVW15] are completely insecure against a general functional encryption adversary (i.e. in the “strong attribute hiding” game). We demonstrate three different attacks, the strongest of which is applicable even to the inner product predicate encryption scheme [AFV11]. Our attacks are practical and allow the attacker to completely recover a from its encryption Enc(a) within a polynomial number of queries. This illustrates that the barrier between predicate and functional encryption is not just a limitation of proof techniques. 2. We provide a new construction that unifies and extends the constructions of Gorbunov et al. [GVW15] and Goldwasser et al. [GTKP+13]. Our construction supports a single “decryption query” as in [GTKP+13] in addition to an unbounded number of “non-decryption queries” as in [GVW15]. In particular, our construction yields an alternate candidate for reusable garbled circuits. 3. We upgrade the security of our construction, as well as [AFV11, GVW15], from selective to semi-adaptive, where the adversary may output the challenge after seeing the public parameters in the security game. Our transformation is generic, and applies to several LWE based selectively secure FE schemes. 4. We generalise the above scheme to support q decryption queries, for any polynomial q which is a-priori fixed. The ciphertext size grows as O(q^2), improving upon the q-query version of [GTKP+13, GVW12] in which the ciphertext size grows as O(q^4). Our ciphertext is succinct in that its size does not depend on the size of the circuit.