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:
- 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).
- 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.
- 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