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.Category / Keywords: public-key cryptography / functional encryption, learning with errors, predicate encryption Date: received 26 Jun 2016, last revised 22 Sep 2016 Contact author: shwetaa at gmail com Available format(s): PDF | BibTeX Citation Version: 20160922:091343 (All versions of this report) Short URL: ia.cr/2016/654 Discussion forum: Show discussion | Start new discussion