Sergey Gorbunov
Skip Abstract Section
Abstract
In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an ℓ-bit public index ind and a message m, and a secret key is associated with a Boolean predicate P. The secret key allows decrypting the ciphertext and learning m if and only if P(ind) = 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.
- Shweta Agrawal, Dan Boneh, and Xavier Boyen. 2010a. Efficient lattice (H)IBE in the standard model. In Proceedings of EUROCRYPT. 553--572. Google Scholar
Digital Library
- Shweta Agrawal, Dan Boneh, and Xavier Boyen. 2010b. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In Proceedings of CRYPTO. 98--115. Google ScholarDigital Library
- Shweta Agrawal, Xavier Boyen, Vinod Vaikuntanathan, Panagiotis Voulgaris, and Hoeteck Wee. 2012. Functional encryption for threshold functions (or, fuzzy IBE) from lattices. In Proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography. 280--297. Google ScholarDigital Library
- Shweta Agrawal, David Mandell Freeman, and Vinod Vaikuntanathan. 2011. Functional encryption for inner product predicates from learning with errors. In Proceedings of ASIACRYPT. 21--40. Google ScholarDigital Library
- Miklós Ajtai. 1999. Generating hard instances of the short basis problem. In Proceedings of ICALP. 1--9. Google ScholarDigital Library
- Miklós Ajtai, Ravi Kumar, and D. Sivakumar. 2001. A sieve algorithm for the shortest lattice vector problem. In Proceedings of STOC. 601--610. Google ScholarDigital Library
- Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. 2009. Simultaneous hardcore bits and cryptography against memory attacks. In Proceedings of 6th Theory of Cryptography Conference (TCC09). 474--495. Google ScholarDigital Library
- Joseph A. Akinyele, Matthew W. Pagano, Matthew D. Green, Christoph U. Lehmann, Zachary N. J. Peterson, and Aviel D. Rubin. 2011. Securing electronic medical records using attribute-based encryption on mobile devices. In Proceedings of the 1st ACM Workshop on Security and Privacy in Smartphones and Mobile Devices (SPSM'11). ACM, New York, NY, 75--86. DOI:http://dx.doi.org/10.1145/2046614.2046628 Google ScholarDigital Library
- Prabhanjan Ananth, Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan. 2014. From selective to adaptive security in functional encryption. Cryptology ePrint Archive: Report 2014/917. (2014).Google Scholar
- Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2010. From secrecy to soundness: Efficient verification via secure computation. In Proceedings of ICALP. 152--163. Google ScholarDigital Library
- Giuseppe Ateniese, Kevin Fu, Matthew Green, and Susan Hohenberger. 2006. Improved proxy re-encryption schemes with applications to secure distributed storage. ACM Trans. Inf. Syst. Secur. 9, 1 (2006), 1--30. Google ScholarDigital Library
- Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. 2012. Foundations of garbled circuits. In Proceedings of the ACM CCS. 784--796. Google ScholarDigital Library
- Matt Blaze, Gerrit Bleumer, and Martin Strauss. 1998. Divertible protocols and atomic proxy cryptography. In Proceedings of EUROCRYPT. 127--144.Google ScholarCross Ref
- Dan Boneh and Xavier Boyen. 2004. Efficient selective-ID secure identity-based encryption without random oracles. In Proceedings of EUROCRYPT. 223--238.Google ScholarCross Ref
- Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. 2004. Public key encryption with keyword search. In Advances in Cryptology - Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (Eurcorypt'04). 506--522.Google ScholarCross Ref
- Dan Boneh and Matthew K. Franklin. 2001. Identity-based encryption from the Weil pairing. In Proceedings of CRYPTO. 213--229. Google ScholarDigital Library
- Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. 2014. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Proceedings of EUROCRYPT.Google ScholarCross Ref
- Dan Boneh, Amit Sahai, and Brent Waters. 2011. Functional encryption: Definitions and challenges. In Proceedings of TCC. 253--273. Google ScholarDigital Library
- Xavier Boyen. 2013. Attribute-based functional encryption on lattices. In Proceedings of TCC. 122--142. Google ScholarDigital Library
- Zvika Brakerski and Vinod Vaikuntanathan. 2011. Efficient fully homomorphic encryption from (standard) LWE. In Proceedings of FOCS. 97--106. Google ScholarDigital Library
- David Cash, Dennis Hofheinz, and Eike Kiltz. 2009. How to delegate a lattice basis. Cryptology ePrint Archive, Report 2009/351. (2009).Google Scholar
- David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. 2012. Bonsai trees, or how to delegate a lattice basis. J. Cryptol. 25, 4 (2012), 601--639. Google ScholarDigital Library
- Kai-Min Chung, Yael Kalai, and Salil P. Vadhan. 2010. Improved delegation of computation using fully homomorphic encryption. In Proceedings of CRYPTO. 483--501. Google ScholarDigital Library
- Clifford Cocks. 2001. An identity based encryption scheme based on quadratic residues. In Proceedings of the IMA International Conference. 360--363. Google ScholarDigital Library
- Jean-Sbastien Coron, Tancrde Lepoint, and Mehdi Tibouchi. 2013. Practical multilinear maps over the integers. In Advances in Cryptology - (CRYPTO'13), Ran Canetti and Juan A. Garay (Eds.). Lecture Notes in Computer Science, Vol. 8042. Springer, Berlin Heidelberg, 476--493. DOI:http://dx.doi.org/10.1007/978-3-642-40041-4_26Google Scholar
- Sanjam Garg, Craig Gentry, and Shai Halevi. 2012. Candidate multilinear maps from ideal lattices and applications. Cryptology ePrint Archive, Report 2012/610. (2012).Google Scholar
- Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai, and Brent Waters. 2013. Attribute-based encryption for circuits from multilinear maps. In Proceedings of CRYPTO. 479--499. Also, Cryptology ePrint Archive, Report 2013/128.Google Scholar
- Rosario Gennaro, Craig Gentry, and Bryan Parno. 2010. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Proceedings of CRYPTO. 465--482. Google ScholarDigital Library
- Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In Proceedings of STOC. 169--178. Google ScholarDigital Library
- Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of STOC. 197--206. Google ScholarDigital Library
- Shafi Goldwasser, Yael Kalai, Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. 2013. Succinct functional encryption and its power: Reusable garbled circuits and beyond. In Proceedings of STOC.Google Scholar
- Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2008. Delegating computation: Interactive proofs for muggles. In Proceedings of STOC. 113--122. Google ScholarDigital Library
- Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2012. Functional encryption with bounded collusions via multi-party computation. In Proceedings of CRYPTO. 162--179.Google ScholarDigital Library
- Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. 2006. Attribute-based encryption for fine-grained access control of encrypted data. In Proceedings of the ACM CCS. 89--98. Google ScholarDigital Library
- Matthew Green, Susan Hohenberger, and Brent Waters. 2011. Outsourcing the decryption of ABE ciphertexts. In Proceedings of the 20th USENIX Conference on Security (SEC'11). USENIX Association. http://dl.acm.org/citation.cfm?id=2028067.2028101. Google ScholarDigital Library
- Susan Hohenberger, Guy N. Rothblum, Abhi Shelat, and Vinod Vaikuntanathan. 2011. Securely obfuscating re-encryption. J. Cryptol. 24, 4 (2011), 694--719. Google ScholarDigital Library
- Jonathan Katz, Amit Sahai, and Brent Waters. 2008. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In Proceedings of EUROCRYPT. 146--162. Google ScholarDigital Library
- Allison B. Lewko, Tatsuaki Okamoto, Amit Sahai, Katsuyuki Takashima, and Brent Waters. 2010. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In Proceedings of EUROCRYPT. 62--91. Google ScholarDigital Library
- Allison B. Lewko and Brent Waters. 2010. New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In Proceedings of TCC. 455--479. Google ScholarDigital Library
- Allison B. Lewko and Brent Waters. 2012. New proof methods for attribute-based encryption: Achieving full security through selective techniques. In Proceedings of CRYPTO. 180--198.Google Scholar
- Ming Li, Shucheng Yu, Yao Zheng, Kui Ren, and Wenjing Lou. 2013. Scalable and secure sharing of personal health records in cloud computing using attribute-based encryption. IEEE Trans. Parallel Distrib. Syst. 24, 1 (2013), 131--143. DOI:http://dx.doi.org/10.1109/TPDS.2012.97 Google ScholarDigital Library
- Silvio Micali. 2000. Computationally sound proofs. SIAM J. Comput. 30, 4 (2000), 1253--1298. Google ScholarDigital Library
- Daniele Micciancio and Chris Peikert. 2012. Trapdoors for lattices: Simpler, tighter, faster, smaller. In Proceedings of EUROCRYPT. 700--718. Google ScholarDigital Library
- Daniele Micciancio and Panagiotis Voulgaris. 2010. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of STOC. 351--358. Google ScholarDigital Library
- Tatsuaki Okamoto and Katsuyuki Takashima. 2010. Fully secure functional encryption with general relations from the decisional linear assumption. In Proceedings of CRYPTO. 191--208. Google ScholarDigital Library
- Adam O'Neill. 2010. Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556. (2010).Google Scholar
- Rafail Ostrovsky and William E. Skeith III. 2005. Private streaming in streaming data. In Advances in Cryptology (CRYPTO'05), Victor Shoup (Ed.). Lecture Notes in Computer Science, Vol. 3621. Springer Berlin Heidelberg, 223--240. Google ScholarDigital Library
- John P. Papanis, Stavros I. Papapanagiotou, Aziz S. Mousas, Georgios V. Lioudakis, Dimitra I. Kaklamani, and Iakovos S. Venieris. 2014. On the use of attribute-based encryption for multimedia content protection over information-centric networks. Trans. Emerg. Telecommu. Techno. 25, 4 (2014), 422--435. DOI: http://dx.doi.org/10.1002/ett.2722 Google ScholarDigital Library
- Bryan Parno, Mariana Raykova, and Vinod Vaikuntanathan. 2012. How to delegate and verify in public: Verifiable computation from attribute-based encryption. In Proceeding of TCC. 422--439. Google ScholarDigital Library
- Chris Peikert. 2009. Public-key cryptosystems from the worst-case shortest vector problem. In Proceeding of STOC. 333--342. Google ScholarDigital Library
- Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 6 (2009). Google ScholarDigital Library
- Alon Rosen and Gil Segev. 2010. Chosen-ciphertext security via correlated products. SIAM J. Comput. 39, 7 (2010), 3058--3088. Google ScholarDigital Library
- Amit Sahai and Hakan Seyalioglu. 2010. Worry-free encryption: Functional encryption with public keys. In Proceeding of the ACM CCS. 463--472. Google ScholarDigital Library
- Amit Sahai and Brent Waters. 2005. Fuzzy identity-based encryption. In Proceeding of EUROCRYPT. 457--473. Google ScholarDigital Library
- Adi Shamir. 1984. Identity-based cryptosystems and signature schemes. In Proceeding of CRYPTO. 47--53. Google ScholarDigital Library
- Damien Stehlé and Ron Steinfeld. 2010. Faster fully homomorphic encryption. In Proceeding of ASIACRYPT. 377--394.Google Scholar
- Brent Waters. 2009. Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In Proceeding of CRYPTO. 619--636. Google ScholarDigital Library
- Brent Waters. 2012. Functional encryption for regular languages. In Proceeding of CRYPTO. 218--235.Google Scholar
Index Terms
- Attribute-Based Encryption for Circuits
Recommendations
Attribute-based encryption for circuits
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingIn 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) ...
Comments on Circuit ciphertext-policy attribute-based hybrid encryption with verifiable delegation
Attribute-based encryption (ABE) with outsourced decryption not only allows fine-grained and versatile sharing of encrypted data, but also largely mitigates the decryption overhead and the ciphertext size in the standard ABE schemes. Very recently, Xu ...
Revocable attribute-based encryption from standard lattices
AbstractAttribute-based encryption (ABE) is an attractive extension of public key encryption, which provides fine-grained and role-based access to encrypted data. In its key-policy flavor, the secret key is associated with an access policy and ...
Highlights- Our scheme is based on the learning with errors (LWE) problem, which is believed to be quantum-resistant.
Comments