Paper 2014/356

Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits

Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy

Abstract

We construct the first (key-policy) attribute-based encryption (ABE) system with short secret keys: the size of keys in our system depends only on the depth of the policy circuit, not its size. Our constructions extend naturally to arithmetic circuits with arbitrary fan-in gates thereby further reducing the circuit depth. Building on this ABE system we obtain the first reusable circuit garbling scheme that produces garbled circuits whose size is the same as the original circuit plus an additive poly(k,d) bits, where k is the security parameter and d is the circuit depth. Save the additive $poly(k,d) factor, this is the best one could hope for. All previous constructions incurred a multiplicative poly(k) blowup. As another application, we obtain (single key secure) functional encryption with short secret keys. We construct our attribute-based system using a mechanism we call fully key-homomorphic encryption which is a public-key system that lets anyone translate a ciphertext encrypted under a public-key x into a ciphertext encrypted under the public-key (f(x),f) of the same plaintext, for any efficiently computable f. We show that this mechanism gives an ABE with short keys. Security is based on the subexponential hardness of the learning with errors problem. We also present a second (key-policy) ABE, using multilinear maps, with short ciphertexts: an encryption to an attribute vector x is the size of x plus poly(k,d) additional bits. This gives a reusable circuit garbling scheme where the size of the garbled input is short, namely the same as that of the original input, plus a poly(k,d) factor.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2014
Keywords
Attribute Based EncryptionABEKey-Homomorphic Public Key EncryptionFunctional Encryptionarithmetic circuitsselective securitylearning with errorsLWElatticesReusable Garbled CircuitsShort Secret KeyShort Ciphertext
Contact author(s)
valerini @ stanford edu
History
2014-06-03: revised
2014-05-22: received
See all versions
Short URL
https://ia.cr/2014/356
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/356,
      author = {Dan Boneh and Craig Gentry and Sergey Gorbunov and Shai Halevi and Valeria Nikolaenko and Gil Segev and Vinod Vaikuntanathan and Dhinakaran Vinayagamurthy},
      title = {Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2014/356},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/356}},
      url = {https://eprint.iacr.org/2014/356}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.