1 Search Results for "Solomon, Tomer"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.17
Bootstrapping Homomorphic Encryption via Functional Encryption

Authors: Nir Bitansky and Tomer Solomon

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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).
Cite as

Nir Bitansky and Tomer Solomon. Bootstrapping Homomorphic Encryption via Functional Encryption. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.17},
  URN =		{urn:nbn:de:0030-drops-175200},
  doi =		{10.4230/LIPIcs.ITCS.2023.17},
  annote =	{Keywords: Fully Homomorphic Encryption, Polynomial Assumptions, Cryptographic Puzzles}
}
  • Refine by Author
  • 1 Bitansky, Nir
  • 1 Solomon, Tomer

  • Refine by Classification
  • 1 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 1 Cryptographic Puzzles
  • 1 Fully Homomorphic Encryption
  • 1 Polynomial Assumptions

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact