Secure Collaborative Intelligence: Evaluating Random Forests via Multi-Key Homomorphic Encryption

TL;DR

In the era of collaborative data science, hospitals or financial institutions often need to pool their models without revealing sensitive parameters or patient data. This paper presents a breakthrough protocol that allows an untrusted cloud to aggregate results from multiple encrypted Random Forest models. By introducing the SecComp and SecCount protocols, the authors reduce interaction to just 2 rounds and significantly boost efficiency through homomorphic parallelization.

Problem & Motivation: The Interaction Bottleneck

Traditional privacy-preserving decision trees rely on additive homomorphic encryption and the DGK protocol. While secure, these methods have a "chatty" nature: the server must stop at every node, ask the client to help decrypt an intermediate bit, and then proceed.

This creates several issues:

1. High Latency: Network round-trips for every tree level.
2. Structural Leaks: The pattern of interaction can reveal tree depth or branching logic.
3. Key Management Rigidness: They don't easily support scenarios where Model A is encrypted with Key 1 and Model B with Key 2.

The authors' insight was to move away from interactive comparisons toward a purely homomorphic logic circuit that can be evaluated "blindfolded" by the cloud.

Methodology: The Core Architecture

The system utilizes Somewhat Homomorphic Encryption (SWHE) based on the BGV scheme. To solve the "multi-party" problem, they use a clever hybrid of Threshold HE and Multi-Key HE.

1. SecComp: Non-Interactive Comparison

Instead of asking the client for help, the cloud evaluates a boolean circuit for $x<y$ directly in the encrypted domain. By translating the comparison into a binary evaluation tree, the multiplicative depth is reduced from linear to logarithmic, allowing for massive parallelization.

Figure: The SecComp evaluation tree structure designed for parallel execution.

2. SecCount: Oblivious Aggregation

For Random Forests, a simple average isn't enough for multi-class classification. The SecCount protocol matches evaluated results against a vector of class labels using XNOR and AND gates, maintaining counts in the encrypted space.

3. Efficiency Optimizations

• Hybrid Encryption: Using AES to transmit data and "homomorphically decrypting" it into SWHE ciphertexts at the cloud level.
• In-Pair Multiplication: Evaluating the tree polynomial in pairs to stay within the "Somewhat" depth limits of the encryption scheme.

Experiments & Results

The authors tested their prototype on real-world datasets (Breast Cancer, Heart Disease).

• Round Complexity: Reduced to a constant 2 rounds, whereas prior SOTA like Tai et al. or Wu et al. required 4 to 6 rounds.
• Parallel Speedup: On an 8-core system, 16-bit comparisons dropped from 328s to just 37s.
• Accuracy: Maintains 100% accuracy relative to plaintext models, as the encryption does not introduce stochastic noise into the threshold logic.

Figure: Performance of SecComp showing the drastic latency reduction as parallel cores increase.

Critical Analysis & Conclusion

The primary takeaway is that Multi-Key SWHE is now practical enough for non-linear models like Random Forests. By shifting the burden from communication (interaction) to computation (parallel homomorphic gates), the protocol becomes viable for high-latency cloud environments.

Limitations:

• The current implementation focuses on integers. Many real-world features are floating-point, which would require the CKKS scheme.
• Computation Cost: While the round complexity is low, the TFLOPS required for homomorphic multiplication remain high.

Future Outlook: This work paves the way for "Confidential Collaborative Learning," where multiple competitors can provide a joint diagnostic service without ever seeing each other's proprietary trees or the user's private features.