License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.17
URN: urn:nbn:de:0030-drops-175200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17520/
Bitansky, Nir ;
Solomon, Tomer
Bootstrapping Homomorphic Encryption via Functional Encryption
Abstract
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 based 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 assuming a generalization of the time-hierarchy theorem, which follows for example from non-uniform ETH.
At the heart of the construction is a new proof technique based on cryptographic puzzles and decomposable obfuscation. 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).
BibTeX - Entry
@InProceedings{bitansky_et_al:LIPIcs.ITCS.2023.17,
author = {Bitansky, Nir and Solomon, Tomer},
title = {{Bootstrapping Homomorphic Encryption via Functional Encryption}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {17:1--17:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17520},
URN = {urn:nbn:de:0030-drops-175200},
doi = {10.4230/LIPIcs.ITCS.2023.17},
annote = {Keywords: Fully Homomorphic Encryption, Polynomial Assumptions, Cryptographic Puzzles}
}
|
Keywords: |
|
Fully Homomorphic Encryption, Polynomial Assumptions, Cryptographic Puzzles |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
