Attribute-based encryption for circuits

By Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee. Symposium on the Theory of Computing, 2013

500 citations recorded by the source corpus.

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an l-bit public index pind and a message m, and a secret key is associated with a Boolean predicate P. The secret key allows to decrypt the ciphertext and learn m iff P(pind) = 1. Moreover, the scheme should be secure against collusions of users, namely, 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 attribute-based encryption schemes for circuits of any arbitrary polynomial size, where the public parameters and the ciphertext grow linearly with the depth of the circuit. Our construction is secure under the standard learning with errors (LWE) assumption. Previous constructions of attribute-based encryption were for Boolean formulas, captured by the complexity class NC1. In the course of our construction, we present a new framework for constructing ABE schemes. As a by-product of our framework, we obtain ABE schemes for polynomial-size branching programs, corresponding to the complexity class LOGSPACE, under quantitatively better assumptions.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/9e5d1f10be1ac1bae1a219e2426ef5893f077ac4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Lattice Signatures and Bimodal Gaussians (2013, background): “In addition, researchers are rapidly discovering new lattice-based primitives, such as fully-homomorphic encryption [10], multi-linear maps [9], and attribute-based encryption [14], that had no previous constructions based on classical numbertheoretic techniques.”
Multi-Input Functional Encryption (2014, background): “) The past few years have seen steady progress toward constructing predicate encryption schemes [24, 19, 18, 20] and FE schemes [31, 23, 21, 20] with greater expressiveness and collusion resistance, culminating in the recent work of Garg et al.”
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (2012, background): “Many lattice-based primitives based on LWE have been discovered, such as public-key encryption [25,16,20], (hierarchical) identity-based encryption [16,1,12], functional encryption [3,2,5,17] and fully homomorphic encryption [9,7,6,10].”
TFHE: Fast Fully Homomorphic Encryption Over the Torus (2019, background): “Due to an asymmetry in the noise propagation, it was noticed in [8,15,35] that GSW ciphertext is particularly suited to evaluate long chains of products, or branching programs.”
Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits (2013, result): “Prior solutions for (the weaker) primitives of ABE for circuits [GVW13, GGH + 13b] and single use functional encryption [GKP + 13] achieved ciphertexts sizes and encryption times that were proportional to the maximum depth of the function to be evaluated.”
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits (2014, methodology): “In previous ABE systems for circuits [GVW13, GGH + 13c] secret keys grew as O ( d 2 s ) where s is the number of boolean gates or wires in the circuit.”
Reusable garbled circuits and succinct functional encryption (2013, methodology): “We remark that [30] gives a restricted form of reusable circuit garbling: it provides authenticity of the circuit output, but does not provide input privacy or circuit privacy, as we do here.”
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds (2016, background): “Interestingly, these circuits were historically obtained in [20, 10, 16] with the internal product of GSW, as an optimization which takes advantage of the unbalanced coefficients in the noise recurrence formula.”