Our construction implies:
1. A new construction for reusable garbled circuits that achieves stronger security than the only known prior construction [GKP + 13].
2. A new construction for bounded collusion functional encryption with substantial efficiency benefits: our public parameters and ciphertext size incur an additive growth of O(Q^2), where Q is the number of permissible queries. Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of O (Q^4) in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than GVW12].
Additionally, 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 x from its encryption Enc (x) within a polynomial number of queries. This illustrates that the barrier between predicate and functional encryption is not just a limitation of proof techniques. We believe these attacks shed significant light on the barriers to achieving full fledged functional encryption from LWE, even for simple functionalities such as inner product zero testing [KSW08, AFV11].
Along the way, we develop a new proof technique that permits the simulator to program public parameters based on keys that will be requested in the future. This technique may be of independent interest.Category / Keywords: public-key cryptography / functional encryption, learning with errors, predicate encryption Date: received 26 Jun 2016, last revised 16 Apr 2017 Contact author: shweta a at gmail com Available format(s): PDF | BibTeX Citation Version: 20170416:140704 (All versions of this report) Short URL: ia.cr/2016/654 Discussion forum: Show discussion | Start new discussion