License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.100
URN: urn:nbn:de:0030-drops-91047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9104/
Go to the corresponding LIPIcs Volume Portal

Miccianco, Daniele ; Sorrell, Jessica

Ring Packing and Amortized FHEW Bootstrapping

pdf-format:
LIPIcs-ICALP-2018-100.pdf (0.5 MB)

Abstract

The FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) offers very fast homomorphic NAND-gate computations (on encrypted data) and a relatively fast refreshing procedure that allows to homomorphically evaluate arbitrary NAND boolean circuits. Unfortunately, the refreshing procedure needs to be executed after every single NAND computation, and each refreshing operates on a single encrypted bit, greatly decreasing the overall throughput of the scheme. We give a new refreshing procedure that simultaneously refreshes n FHEW ciphertexts, at a cost comparable to a single-bit FHEW refreshing operation. As a result, the cost of each refreshing is amortized over n encrypted bits, improving the throughput for the homomorphic evaluation of boolean circuits roughly by a factor n.

BibTeX - Entry

@InProceedings{miccianco_et_al:LIPIcs:2018:9104,
  author =	{Daniele Miccianco and Jessica Sorrell},
  title =	{{Ring Packing and Amortized FHEW Bootstrapping}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{100:1--100:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9104},
  URN =		{urn:nbn:de:0030-drops-91047},
  doi =		{10.4230/LIPIcs.ICALP.2018.100},
  annote =	{Keywords: homomorphic encryption, bootstrapping, lattice-based cryptography}
}

Keywords: homomorphic encryption, bootstrapping, lattice-based cryptography
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI