Ripple: Accelerating Programmable Bootstraps for FHE with Wavelet Approximations

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 realistic applications, such as logistic regression and Euclidean distance.

1. 1.

   We empirically observed even 32-bit encrypted LUTs with the state-of-the-art TFHE-rs [32] FHE library require approximately 515 GB of RAM and 65 min. For reference, 30-bit LUTs took almost 15 min requiring over 120 GB..

2. 2.

   An orthogonal matrix M has the property that \(M M^T = I\), where I is the identity matrix. A matrix M is orthogonal if its transpose (\(M^T\)) is equal to its inverse (\(M^{-1}\)).

Authors and Affiliations

1. University of Delaware, Newark, USA

   Charles Gouert & Nektarios G. Tsoutsos

2. Nillion, Zug, Switzerland

   Mehmet Ugurbil, Dimitris Mouris & Miguel de Vega

Corresponding author

Correspondence to Charles Gouert .

Editors and Affiliations

1. Strativia, NIST Associate, Largo, MD, USA

   Nicky Mouha

2. Stony Brook University, Stony Brook, NY, USA

   Nick Nikiforakis

A Evaluation of Applications

Euclidean Distance. This application constitutes a formula for computing the distance between two n-dimensional points \(\boldsymbol{u}\) and \(\boldsymbol{v}\) in the Euclidean space. It has a plethora of applications from statistics and cluster analysis [4] to facial recognition [25] and has drawn the interest of recent FHE works [17, 29]. The Euclidean distance can be computed by \(d(\boldsymbol{u}, \boldsymbol{v}) = \sqrt{\sum _{i=1}^n (u_i - v_i)^2 }\); however, computing non-linearities (e.g., the square root) in the encrypted domain is not a trivial task. Thus, many prior FHE works resort to computing the squared Euclidean distance and return it to the user, who needs to compute the final square root in the clear.

Runtime comparisons for Euclidean distance between Ripple’s three variants (Quantization, Haar DWT, and Biorthogonal DWT), TFHE-rs (baseline), HELM, Google Transpiler, and Romeo for vectors of 32 and 64 elements. Note that HELM, Transpiler, and Romeo only implement the squared Euclidean distance (i.e., without the square root computation). We use a word size \(\textsf{W} \) of 32 bits for all frameworks. Lastly, for 32 and 64 bits, TFHE-rs is not applicable (N/A) as the resources required for the LUT are impractical (see footnote 1).

Full size image

For this benchmark, shown in Fig. 5, we use \(\textsf{W} = 32\) bits and use vector lengths 32 and 64 to demonstrate scalability. All Ripple variants perform the full Euclidean distance computation, while the related works compute the squared Euclidean distance and neglect the final square root calculation. We note that the TFHE-rs baseline is unable to evaluate the Euclidean distance with the required wordsize due to the astronomical cost of building 32-bit encrypted LUTs. For the Google Transpiler, we utilize both logic synthesis backends (i.e., Google XLS and Yosys), which optimize the circuit in different ways. For HELM, we utilize both LUT circuit modes (i.e., many-to-many LUTs for the arithmetic mode and a circuit of 2:1 LUTs for “lossless bidirectional bridging” or LBB). Overall, all three Ripple configurations outperform the related works in terms of latency while still taking into account the square root operation. However, as we observed in Table 1 the Haar and Biorthogonal approaches achieve significantly better approximations than the quantization variant. Notably, Haar also exhibits very competitive latencies across all non-linear functions and benchmarks.

Runtime comparisons for the logistic regression application for 4 attributes for word sizes of 16, 24, and 32 bits. For 24 bits, the arithmetic mode of HELM as well as both modes of the Google Transpiler are not applicable (N/A) as they rely on native word sizes. Lastly, for 32 bits, the TFHE-rs baseline is also N/A as the resources required for the LUT are impractical (see footnote 1).

Full size image

Logistic Regression. Logistic Regression (LR) is a widely studied application in FHE from genome-wide association studies [23] to more generic applications [17, 29] such as natural language processing [1]. This construction is well-suited to binary classification problems and is akin to a single-layer neural network with a sigmoid activation. In Ripple, we use DWT-encoded LUTs to directly compute the sigmoid activation function. The client decrypts the result, which represents the probability that the encrypted input belongs to the first class.

We utilize the Palmer penguin dataset [21], where each input consists of eight attributes that correspond to the physical characteristics of penguins (e.g., bill length, flipper length, etc.). Since logistic regression is particularly well-suited for binary classification, we remove entries in the dataset corresponding to the Chinstrap species. Figure 6 showcases our LR inference benchmark for four attributes. While our chosen dataset is composed of entries with eight attributes, we truncate it to match the dimensions used in related works. We observe that Ripple is significantly faster than related works and also outperforms the TFHE-rs baseline using the full-bit width. The only exception is \(\textsf{W} = 16\) bits, where the baseline outperforms the Biorthogonal DWT; however, for 24 bits, the Biorthogonal DWT exhibits lower latency than the baseline.

To achieve high accuracy with our chosen dataset we utilize all eight attributes with a wordsize of 24 bits. For this binary classification, all modes achieve 100% accuracy; the baseline latency is 13.3 s per inference, while the Biorthogonal DWT variant classifies in 7.8 s. Lastly, the quantized variant that truncates half of the bits of the LUT input exhibits a latency of 6.2 s, while the Haar DWT slightly outperforms this with a latency of approximately 6 s.

Reprints and permissions

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics