2026-07-23T06:23:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9104 2024-03-06T10:43:22Z ddc:004 open_access

Ring Packing and Amortized FHEW Bootstrapping Miccianco, Daniele Sorrell, Jessica homomorphic encryption bootstrapping lattice-based cryptography 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniele Miccianco and Jessica Sorrell 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.100 urn:nbn:de:0030-drops-91047 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.100 eng https://creativecommons.org/licenses/by/3.0/legalcode