cispa_all_3057.pdf (407.45 kB)

Candidate iO from Homomorphic Encryption Schemes

Download (407.45 kB)
conference contribution
posted on 2023-11-29, 18:12 authored by Zvika Brakerski, Nico DöttlingNico Döttling, Sanjam Garg, Giulio Malavolta
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 fullyhomomorphic 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 Damg˚ard-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.


Preferred Citation

Zvika Brakerski, Nico Döttling, Sanjam Garg and Giulio Malavolta. Candidate iO from Homomorphic Encryption Schemes. In: International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT). 2020.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3057, title = "Candidate iO from Homomorphic Encryption Schemes", author = "Brakerski, Zvika and Döttling, Nico and Garg, Sanjam and Malavolta, Giulio", booktitle="{International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)}", year="2020", }

Usage metrics


    No categories selected


    Ref. manager