Generating One-Hot Maps under Encryption

Ehud Aharoni, Nir Drucker, Eyal Kushnir, Ramy Masalha, Hayim Shaul

Abstract

Privacy-Preserving Machine Learning (PPML) leveraging Homomorphic Encryption (HE) often encounters a fundamental trade-off between communication bandwidth and computational latency. This paper presents efficient methodologies for generating and managing "one-hot maps" within HE environments, specifically targeting the CKKS scheme. By utilizing the Chinese Remainder Theorem (CRT) and novel tree-based conversion algorithms, we demonstrate a path to significantly reducing the bandwidth overhead of encrypted one-hot encoding without the prohibitive latency associated with traditional server-side conversion.

Introduction

The rise of cloud-based AI has necessitated robust privacy measures. Homomorphic Encryption (HE) allows servers to process data without ever seeing the underlying plaintext. However, HE is computationally intensive, particularly for non-linear operations like comparisons. In decision tree models, which are foundational to many machine learning tasks, these comparisons are ubiquitous.

To optimize these operations, researchers frequently employ one-hot encoding. For instance, a numerical value $x=3$ is represented as a vector $[0, 0, 0, 1, 0]$. This transformation converts complex comparisons into efficient bit-checks. However, this introduces the Bandwidth-Latency Seesaw:

  1. High Bandwidth: If the client uploads pre-computed one-hot maps, the data volume is massive (e.g., a vector of size 10,000 for a single feature).
  2. High Latency: If the client uploads a single numeric value to save bandwidth, the server must perform a "numeric-to-one-hot" conversion, which is computationally expensive under HE.

Proposed Methodologies

CRT-based Representation

To find a middle ground, we propose a representation based on the Chinese Remainder Theorem (CRT). Instead of a single one-hot vector of size $n$, the client transmits several smaller one-hot vectors corresponding to the coprime factors of $n$. For a value range up to 10,000, a client might send five small maps totaling only 38 slots. The server then expands these into the full map, balancing the communication load and server-side processing.

Tree-based Lagrange Interpolation

For server-side conversion of encrypted numbers into one-hot maps, we utilize Lagrange polynomials. We introduce two tree-based algorithms to optimize this process, utilizing a "tile tensor" data structure to maximize SIMD (Single Instruction, Multiple Data) efficiency within HE ciphertexts.

Figure 1: A hierarchical tree structure used for efficient polynomial computation in one-hot map generation.
  • Algorithm 1 ("Shallow but big"): Focuses on minimizing multiplication depth ($\log n$), which is critical for HE schemes like CKKS, though it requires more total multiplications ($n \log n$).
  • Algorithm 2 ("Small but less shallow"): Optimizes for total computational cost, reducing multiplications to $2n$ while slightly increasing the depth to $2 \log n$.

Experimental Results

Our benchmarks focused on algorithmic efficiency and bandwidth requirements using synthetic parameters ranging from $n=100$ to $n=10,000$.

Bandwidth Efficiency

The CRT representation shows dramatic improvements. For a range of $n=10,000$, the standard one-hot map requires 10,000 ciphertext slots. In contrast, the CRT approach requires only 38 slots, representing a nearly 260x reduction in client-to-server data transfer.

Latency Performance

In terms of server-side computation, Algorithm 2 consistently outperforms traditional "Equality" operator approaches. For $n=64$, our tree-based approach completed the conversion in approximately 25 seconds, compared to over 50 seconds for the standard method. The tree-based algorithms maintained high precision, with errors as low as $10^{-9}$ for smaller values of $n$.

Discussion and Limitations

While these methods offer significant improvements, challenges remain. The tree-based algorithms are sensitive to numerical overflow in the CKKS scheme as $n$ increases. We addressed this using "shadow trees"—pre-computed plaintext trees—to stabilize calculations up to larger values of $n$. However, precision naturally degrades as the polynomial degree increases.

Furthermore, this study focuses on the generation of one-hot maps. Future work should evaluate the end-to-end performance within a complete decision tree inference pipeline and explore varied "tile shapes" for data arrangement in ciphertexts.

Conclusion

By leveraging CRT representations and optimized tree-based Lagrange interpolation, we provide a scalable solution to the one-hot encoding problem in HE. These techniques effectively balance the bandwidth-latency seesaw, making privacy-preserving decision tree inference more practical for real-world cloud applications.

Summary updated

Abstract

One-hot maps are commonly used in the AI domain. Unsurprisingly, they can also bring great benefits to ML-based algorithms such as decision trees that run under Homomorphic Encryption (HE), specifically CKKS. Prior studies in this domain used these maps but assumed that the client encrypts them. Here, we consider different tradeoffs that may affect the client's decision on how to pack and store these maps. We suggest several conversion algorithms when working with encrypted data and report their costs. Our goal is to equip the ML over HE designer with the data it needs for implementing encrypted one-hot maps.
BibTeX
@inproceedings{aharoni2023generating,
  author = {Ehud Aharoni and Nir Drucker and Eyal Kushnir and Ramy Masalha and Hayim Shaul},
  title = {{Generating One-Hot Maps under Encryption}},
  booktitle = {CSCML},
  year = {2023},
  doi = {10.1007/978-3-031-34671-2\_8},
}
Figure