Paper 2020/394

Candidate iO from Homomorphic Encryption Schemes

Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
Keywords
obfuscationhomomorphic encryption
Contact author(s)
giulio malavolta @ hotmail it
History
2020-04-09: received
Short URL
https://ia.cr/2020/394
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/394,
      author = {Zvika Brakerski and Nico Döttling and Sanjam Garg and Giulio Malavolta},
      title = {Candidate iO from Homomorphic Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/394},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/394}},
      url = {https://eprint.iacr.org/2020/394}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.