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

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

Zeyu Liu, Yunhao Wang

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 …

ciphertext encryption eprint report fully homomorphic encryption homomorphic encryption report single