International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Candidate iO From Homomorphic Encryption Schemes

Authors:
Zvika Brakerski , Weizmann Institute of Science
Nico Döttling , CISPA Helmholtz Center for Information Security
Sanjam Garg , UC Berkeley
Giulio Malavolta , UC Berkeley and Carnegie Mellon University
Download:
DOI: 10.1007/978-3-030-45721-1_4 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: We propose a new approach to construct general-purpose indistinguishability obfuscation (iO). Our construction is obtained via a new intermediate primitive that we call split fully-homomorphic encryption (split FHE), which we show to be sufficient for constructing iO. Specifically, split FHE is FHE where decryption takes the following two-step syntactic form: (i) A secret decryption step uses the secret key and produces a hint which is (asymptotically) shorter than the length of the encrypted message, and (ii) a public decryption step that only requires the ciphertext and the previously generated hint (and not the entire secret key), and recovers the encrypted message. In terms of security, the hints for a set of ciphertexts should not allow one to violate semantic security for any other ciphertexts. Next, we show a generic candidate construction of split FHE based on three building blocks: (i) A standard FHE scheme with linear decrypt-and-multiply (which can be instantiated with essentially all LWE-based constructions), (ii) a linearly homomorphic encryption scheme with short decryption hints (such as the Damgard-Jurik encryption scheme, based on the DCR problem), and (iii) a cryptographic hash function (which can be based on a variety of standard assumptions). Our approach is heuristic in the sense that our construction is not provably secure and makes implicit assumptions about the interplay between these underlying primitives. We show evidence that this construction is secure by providing an argument in an appropriately defined oracle model. We view our construction as a big departure from the state-of-the-art constructions, and it is in fact quite simple.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30242,
  title={Candidate iO From Homomorphic Encryption Schemes},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Obfuscation;Homomorphic Encryption},
  volume={12105},
  doi={10.1007/978-3-030-45721-1_4},
  author={Zvika Brakerski and Nico Döttling and Sanjam Garg and Giulio Malavolta},
  year=2020
}