Paper 2016/654

Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks

Shweta Agrawal


We construct a functional encryption scheme for circuits which simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions: reusable garbled circuits by Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013) [GKP + 13] and predicate encryption for circuits by Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) [GVW15]. Our scheme is secure based on the learning with errors (LWE) assumption. 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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
functional encryptionlearning with errorspredicate encryption
Contact author(s)
shweta a @ gmail com
2017-04-16: last of 2 revisions
2016-06-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal},
      title = {Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/654},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.