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

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