Paper 2023/910

Amortized Functional Bootstrapping in less than 7ms, with $\tilde{O}(1)$ polynomial multiplications

Zeyu Liu, Yale University
Yunhao Wang, Columbia University
Abstract

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed the technique to bootstrap $n$ LWE ciphertexts simultaneously, reducing the total cost from $\tilde{O}(n^2)$ to $\tilde{O}(3^\epsilon n^{1+\frac{1}{\epsilon}})$ for arbitrary $\epsilon > 0$. Several recent works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of them demonstrates the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e. only supporting the evaluation of some specific type of function when performing bootstrapping. In this work, we propose a construction that is not only asymptotically efficient (requiring only $\tilde{O}(n)$ polynomial multiplications for bootstrapping of $n$ LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes $< 5$ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ${\sim}6.7$ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.

Note: Minor editorial changes and typo fixing.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Keywords
Fully Homomorphic EncryptionBootstrapping
Contact author(s)
zeyu liu @ yale edu
yw3736 @ columbia edu
History
2023-10-07: revised
2023-06-12: received
See all versions
Short URL
https://ia.cr/2023/910
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/910,
      author = {Zeyu Liu and Yunhao Wang},
      title = {Amortized Functional Bootstrapping in less than 7ms, with $\tilde{O}(1)$ polynomial multiplications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/910},
      year = {2023},
      url = {https://eprint.iacr.org/2023/910}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.