Abstract
This paper introduces a hybrid cryptographic system designed for privacy-preserving ridge regression on large-scale datasets. By combining linearly homomorphic encryption (LHE) for efficient data aggregation with Yao’s garbled circuits (GC) for complex matrix operations, the proposed framework overcomes the scalability limitations of pure LHE or GC approaches. The system decouples the computational complexity from the number of records, enabling the training of models on 100 million records in less than 9 hours. Experimental results on real-world and synthetic datasets demonstrate significant speedups over existing state-of-the-art methods while maintaining high numerical accuracy.
Introduction
Machine learning often relies on sensitive data collected by service providers. Traditionally, these providers must see the data "in the clear" to train models, posing significant privacy risks. While cryptographic tools like Homomorphic Encryption (HE) and Multi-Party Computation (MPC) exist, they often face a "scalability wall." Pure Garbled Circuits (GC) scale linearly with the number of users ($n$), becoming impractical for millions of records. Conversely, pure HE is efficient for linear additions but struggles with non-linear operations like matrix inversion. This work addresses these challenges by developing a performant ridge regression system capable of handling "Big Data" scales privately.
System Architecture and Methods
The core innovation is a hybrid architecture that splits ridge regression into two distinct phases, utilizing the most efficient cryptographic tool for each task. The system involves three main entities: data-contributing users, an Evaluator, and a Crypto Service Provider (CSP).
Phase 1: Data Aggregation
Users encrypt their local data contributions using a linearly homomorphic scheme (e.g., Paillier). Ridge regression can be formulated as a sum of individual matrices ($A = \sum x_i x_i^T$) and vectors ($b = \sum y_i x_i$). The Evaluator uses the additive property of the encryption to aggregate all user data into a single encrypted global matrix and vector. Crucially, the size of this result depends only on the number of features ($d$), making the subsequent steps independent of the number of users ($n$).
Phase 2: Secure Matrix Solving
The Evaluator and CSP use Yao’s garbled circuits to solve the linear system $A\beta = b$. To optimize this, a "masking" protocol is employed: the Evaluator adds random noise to the encrypted data before sending it to the CSP. The CSP decrypts the "blinded" data, and the garbled circuit subtracts the noise and solves the system using Cholesky decomposition. Cholesky decomposition was chosen for its data-agnostic nature, avoiding conditional branching (pivoting) that would increase circuit complexity.
Experimental Evaluation
The system was evaluated using 24 real-world datasets from the UCI Machine Learning Repository and large-scale synthetic datasets.
Performance and Scalability
The hybrid approach achieves massive speedups. For a dataset with 51,000 records and 22 features, the system completed the task in 3 minutes, compared to 2 days for a previous state-of-the-art secret-sharing implementation. Most impressively, the system successfully processed 100 million records with 20 features in approximately 8.75 hours on a single commodity server.
Accuracy and Efficiency
Using 25-bit fixed-point arithmetic for fractional parts, the system achieved an error rate of less than $10^{-6}$ compared to standard double-precision floating-point calculations. Communication overhead remained practical, with total data exchange between the Evaluator and CSP staying under 300 MB for most UCI datasets.
Discussion and Key Insights
The primary breakthrough is eliminating the $n$-dependency in the most computationally expensive phase (GC). By performing aggregation via HE, the heavy cryptographic lifting becomes independent of the user count. Furthermore, the "masking trick" allows for fast decryption of blinded data outside the GC, significantly reducing overhead.
However, the system relies on a non-collusion assumption between the Evaluator and the CSP. While the paper outlines methods to handle malicious evaluators using zero-knowledge proofs, these additions reintroduce linear scaling with $n$, highlighting a trade-off between security guarantees and performance. Future work may explore extending this hybrid approach to iterative algorithms like Logistic Regression or Support Vector Machines.
Summary updated