Paper 2023/1376

Bootstrapping Homomorphic Encryption via Functional Encryption

Nir bitansky, Tel Aviv University
Tomer Solomon, Tel Aviv University

Homomorphic encryption is a central object in modern cryptography, with far-reaching applications. Constructions supporting homomorphic evaluation of arbitrary Boolean circuits have been known for over a decade, based on standard lattice assumptions. However, these constructions are leveled, meaning that they only support circuits up to some a-priori bounded depth. These leveled constructions can be bootstrapped into fully homomorphic ones, but this requires additional circular security assumptions, which are construction-dependent, and where reductions to standard lattice assumptions are no longer known. Alternative constructions are known based on indistinguishability obfuscation, which has been recently constructed under standard assumptions. However, this alternative requires subexponential hardness of the underlying primitives. We prove a new bootstrapping theorem relying on functional encryption, which is known based on standard polynomial hardness assumptions. As a result we obtain the first fully homomorphic encryption scheme that avoids both circular security assumptions and super-polynomial hardness assumptions. The construction is secure against uniform adversaries, and can be made non-uniformly secure, under a widely-believed worst-case complexity assumption (essentially that non-uniformity does not allow arbitrary polynomial speedup). At the heart of the construction is a new proof technique based on cryptographic puzzles. Unlike most cryptographic reductions, our security reduction does not fully treat the adversary as a black box, but rather makes explicit use of its running time (or circuit size).

Available format(s)
Publication info
Published elsewhere. Major revision. ITCS23
Fully Homomorphic EncryptionFunctional EncryptionIndistinguishability ObfuscationCryptographic Puzzles
Contact author(s)
nbitansky @ gmail com
tomer solomon1 @ gmail com
2023-09-15: approved
2023-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir bitansky and Tomer Solomon},
      title = {Bootstrapping Homomorphic Encryption via Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1376},
      year = {2023},
      doi = {10.4230/LIPIcs.ITCS.2023.17},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.