💻 computer science

HE-DAP: Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization for Statistical Computation

HE-DAP is a cross-platform optimization framework that automatically adapts the trade-off between polynomial evaluation and bootstrapping in homomorphic encryption to significantly accelerate the inverse square root computation and enhance end-to-end performance for privacy-preserving statistical analytics across diverse hardware environments.

Original authors: Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

Published 2026-06-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend, but you can only do it through a very strict, paranoid post office. This post office (the Homomorphic Encryption system) allows you to perform math on your locked boxes without ever opening them. This is great for privacy, but there's a catch: the post office is incredibly slow. Every time you do a calculation, the boxes get heavier and more fragile. If you do too many calculations, the boxes break, and your secret is lost.

One of the most common math problems you need to solve in statistics is finding the inverse square root (think of it as finding the "square root of a fraction"). It's a key step in many data analysis tasks, like figuring out how unusual a specific data point is.

The Problem: A "One-Size-Fits-All" Mistake

Previously, researchers had a recipe for solving this inverse square root problem inside these locked boxes. They called it PP-STAT.

Think of PP-STAT like a fixed recipe for baking a cake. The recipe says: "Use exactly 29 cups of flour and bake for exactly 6 hours."

The Issue: This recipe was tested only in one specific kitchen (a specific computer chip called a CPU using a library called Lattigo). In that kitchen, the recipe worked okay.
The Reality: But what if you move to a different kitchen? Maybe you have a super-fast oven (a GPU) or a different type of stove (a different software library called HEaaN). In these new kitchens, the "29 cups of flour" might take forever to mix, while the "6-hour bake time" might be the slow part.
The Result: Using the same fixed recipe in a new kitchen is inefficient. You might spend 6 hours mixing ingredients when you could have baked it in 1 hour, or vice versa. The paper found that in some environments, the old recipe was nearly 6 times slower than it needed to be because it was doing the wrong thing at the wrong time.

The Solution: HE-DAP (The Smart Kitchen Assistant)

The authors created a new tool called HE-DAP. Think of HE-DAP as a smart kitchen assistant that doesn't just follow a recipe; it tastes the kitchen first.

Before you start your actual work, HE-DAP runs a quick series of tests on the specific computer and software you are using. It asks:

"Is mixing the flour (the math) slow here, or is the baking time (resetting the boxes) slow?"
"If I use less flour but bake longer, is that faster?"
"If I use more flour but bake shorter, is that faster?"

Based on these tests, HE-DAP dynamically writes a new, custom recipe just for your specific machine. It decides exactly how much "flour" (math complexity) and how many "bakes" (iterations) you need to get the perfect cake (accurate result) in the shortest time possible.

How It Works in Plain English

The Trade-off: To keep the secret boxes from breaking, you have two choices:
- Option A: Do a very complex calculation upfront (like using a high-degree polynomial) to get a great starting guess. This is fast if the calculation is easy, but slow if it's hard.
- Option B: Do a simpler calculation, but then "reset" the box (a process called bootstrapping) to keep it from breaking. This reset is very expensive in some kitchens but cheap in others.
The Adaptation: HE-DAP figures out which option is cheaper for your specific computer.
- On a GPU (a super-fast graphics card), the "reset" button is incredibly fast. So, HE-DAP says, "Let's do a simple calculation and hit the reset button often!"
- On a CPU (a standard processor), the "reset" button is slow. So, HE-DAP says, "Let's do a complex calculation upfront so we don't have to hit the reset button as much!"

The Results: Faster and Smarter

The paper tested this new "Smart Assistant" on three different types of computer setups:

Lattigo (Standard CPU): It made the process 1.96 times faster.
HEaaN-CPU: It made the process 2.18 times faster.
HEaaN-GPU: It made the process 2.35 times faster.

Crucially, it didn't just make things faster; it kept the results just as accurate. In fact, in some cases, it was even more accurate than the old fixed recipe because it avoided the errors that come from forcing a bad recipe onto a new machine.

Why This Matters

The paper shows that for privacy-preserving data analysis to work in the real world, we can't just use one static set of rules. We need systems that can adapt to the hardware they are running on. HE-DAP proves that by automatically tuning these settings, we can make privacy-preserving statistics practical and efficient, turning a slow, clunky process into something that runs nearly twice as fast without sacrificing security or accuracy.

In short: HE-DAP is the tool that stops you from using a heavy winter coat in the summer and a light t-shirt in the winter. It checks the weather (your computer environment) and gives you the perfect outfit (the math parameters) to get the job done quickly and comfortably.

Technical Summary: HE-DAP

Problem Statement

Homomorphic encryption (HE) enables privacy-preserving analytics on encrypted data but suffers from high computational overhead. A critical bottleneck in statistical and machine learning workloads is the computation of the inverse square root ( $1/\sqrt{a}$ ), a fundamental operation required for functions such as Z-score normalization, skewness, kurtosis, and the Pearson correlation coefficient.

Existing state-of-the-art methods, such as PP-STAT [13] and HEaaN-STAT [24], rely on fixed parameter configurations for the inverse square root computation. These configurations typically involve a specific degree for the Chebyshev polynomial approximation (used to initialize Newton's method) and a fixed number of Newton-Raphson iterations. The authors identify a fundamental flaw in this static approach: the relative computational costs of the two primary HE operations—Chebyshev polynomial evaluation and bootstrapping (noise management)—vary drastically (by up to 6 $\times$ ) across different HE libraries (e.g., Lattigo vs. HEaaN) and hardware environments (CPU vs. GPU).

Consequently, a configuration optimized for one environment (e.g., Lattigo on CPU, where bootstrapping is slow and high-degree polynomials are preferred) becomes sub-optimal or inefficient in another (e.g., HEaaN-GPU, where bootstrapping is fast and polynomial evaluation is the bottleneck). This environmental dependency renders existing frameworks non-generalizable and inefficient when deployed across heterogeneous systems.

Methodology: HE-DAP

To address this, the authors propose HE-DAP (Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization), a cross-platform framework that automatically determines the optimal parameters for the inverse square root computation based on the specific execution environment.

Core Mechanism

HE-DAP operates during a provisioning stage (prior to actual data processing) to profile the target server's performance characteristics. It dynamically selects three key parameters for the CryptoInvSqrt algorithm:

$d$ : The degree of the Chebyshev polynomial approximation.
$c$ : A binary indicator for Pre-Bootstrapping (applying bootstrapping to the input ciphertext before the inverse square root computation).
$i$ : The number of Newton-Raphson iterations.

Algorithmic Workflow

Profiling: HE-DAP evaluates all possible input ciphertext levels ( $l$ ) ranging from $l_{BTS} + 1$ to $l_{max}$ .
Search Space Exploration: For each level, it tests combinations of polynomial degrees ( $d$ $d$ ), Pre-BTS indicators ( $c$ $c$ ), and iteration counts ( $i$ $i$ ).
- If the input level is insufficient for the polynomial depth, it considers Pre-BTS ( $c=1$ ).
- If the level is sufficient, it proceeds without Pre-BTS ( $c=0$ ).
Optimization Criteria: For each combination, the system measures the Mean Relative Error (MRE) and runtime. It identifies the optimal iteration count ( $i$ ) that satisfies a target MRE threshold.
Parameter Selection: The framework records two optimal tuples for each level:
- Accuracy-Oriented: Minimizes runtime subject to a strict MRE constraint.
- Speed-Oriented: Minimizes runtime regardless of MRE (useful for applications tolerating higher error).
Runtime Application: During actual statistical analysis, the server uses the pre-computed optimal parameters corresponding to the current ciphertext level, eliminating the need for manual tuning or fixed, sub-optimal defaults.

Key Contributions

HE-DAP Framework: The introduction of a novel adaptive optimizer that automatically configures the inverse square root operation for diverse HE libraries and hardware, moving away from static, environment-specific parameters.
Performance Gains: Demonstration that HE-DAP significantly accelerates the core inverse square root computation. In the HEaaN-GPU environment, it achieves up to a 2.35 $\times$ speedup over the fixed configuration in PP-STAT while maintaining high numerical accuracy (MRE $\le 3.1 \times 10^{-8}$ ).
Comprehensive Evaluation: A rigorous evaluation across three distinct settings (Lattigo, HEaaN-CPU, and HEaaN-GPU) and four core statistical measures (Z-score, skewness, kurtosis, Pearson correlation). The results confirm that HE-DAP consistently discovers optimal configurations for both CPU and GPU environments.
Open Source: The release of the full HE-DAP implementation to ensure reproducibility.

Experimental Results

The authors evaluated HE-DAP against PP-STAT (Lattigo-based) and HEaaN-STAT (GPU-based) using the CKKS scheme.

Inverse Square Root Performance:
- HEaaN-GPU: HE-DAP accelerated PP-STAT by 2.35 $\times$ at level 12 and 1.79 $\times$ at level 7 (accuracy-oriented) compared to the fixed PP-STAT configuration. Compared to HEaaN-STAT, it achieved up to 2.15 $\times$ faster runtime with lower MRE.
- HEaaN-CPU: Achieved a 2.18 $\times$ speedup over PP-STAT at level 12.
- Lattigo: Achieved a 1.96 $\times$ speedup over PP-STAT at level 11, while simultaneously reducing MRE by 79 $\times$ compared to the baseline PP-STAT.
End-to-End Statistical Analysis:
- Applying HE-DAP to statistical measures (ZNorm, Skew, Kurt, PCC) on real-world datasets (UCI Adult and Medical Cost Insurance) resulted in consistent acceleration.
- On the Adult dataset, HE-DAP reduced runtime by 42%–44% compared to PP-STAT while maintaining similar MRE.
- On the Insurance dataset, runtime reductions reached 44.6%.
Trade-off Analysis: The "Speed-Oriented" mode allowed for even greater acceleration (up to 6.34 $\times$ over HEaaN-STAT on GPU) at the cost of increased MRE, demonstrating the framework's flexibility for different application requirements.

Significance and Claims

The paper claims that HE-DAP demonstrates that principled parameter optimization can make privacy-preserving statistical analytics practical at scale. By automating the adaptation to heterogeneous execution environments, HE-DAP resolves the inefficiency caused by fixed parameters in existing frameworks.

The authors emphasize that their approach is environment-aware, acknowledging that the optimal balance between polynomial evaluation and bootstrapping is not universal but contingent on the specific HE library and hardware. By dynamically navigating this trade-off, HE-DAP ensures that the fundamental building block of statistical analysis (inverse square root) is executed with maximum efficiency, thereby enhancing the performance of complex, end-to-end statistical workflows without compromising the privacy guarantees of Homomorphic Encryption.

The paper concludes that while the provisioning phase (parameter search) incurs a time cost (particularly in CPU libraries like Lattigo), this is a one-time setup cost that yields significant, sustained performance benefits during the actual data processing phase. Future work is suggested to reduce this exploration time by leveraging measurable proxies for performance rather than exhaustive evaluation.