Paper 2024/866
Ripple: Accelerating Programmable Bootstraps for FHE with Wavelet Approximations
Abstract
Homomorphic encryption can address key privacy challenges in cloud-based outsourcing by enabling potentially untrusted servers to perform meaningful computation directly on encrypted data. While most homomorphic encryption schemes offer addition and multiplication over ciphertexts natively, any non-linear functions must be implemented as costly polynomial approximations due to this restricted computational model. Nevertheless, the CGGI cryptosystem is capable of performing arbitrary univariate functions over ciphertexts in the form of lookup tables through the use of programmable bootstrapping. While promising, this procedure can quickly become costly when high degrees of precision are required. To address this challenge, we propose Ripple: a framework that introduces different approximation methodologies based on discrete wavelet transforms (DWT) to decrease the number of entries in homomorphic lookup tables while maintaining high accuracy. Our empirical evaluations demonstrate significant error reduction compared to plain quantization methods across multiple non-linear functions. Notably, Ripple improves runtime performance for several realistic benchmarks, such as logistic regression and cross-correlation, among others.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. 27th Information Security Conference (ISC)
- DOI
- 10.1007/978-3-031-75757-0_14
- Keywords
- Applied CryptographyHomomorphic EncryptionLookup TablesPrivacy-Enhancing TechnologiesEncrypted Computation
- Contact author(s)
-
cgouert @ udel edu
memo @ nillion com
dimitris @ nillion com
miguel @ nillion com
tsoutsos @ udel edu - History
- 2024-11-01: last of 2 revisions
- 2024-05-31: received
- See all versions
- Short URL
- https://ia.cr/2024/866
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/866,
author = {Charles Gouert and Mehmet Ugurbil and Dimitris Mouris and Miguel de Vega and Nektarios Georgios Tsoutsos},
title = {Ripple: Accelerating Programmable Bootstraps for {FHE} with Wavelet Approximations},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/866},
year = {2024},
doi = {10.1007/978-3-031-75757-0_14},
url = {https://eprint.iacr.org/2024/866}
}