TL;DR
This paper introduces the first privacy-preserving matrix factorization protocol using fully homomorphic encryption (FHE). It allows recommendation systems to compute user and item profiles from encrypted user ratings, ensuring that neither the system nor a third-party service provider can access the raw data, thus protecting user privacy without sacrificing recommendation accuracy.
What Problem Does This Paper Address?
Recommendation systems, ubiquitous in daily life (e.g., movie and product suggestions), rely heavily on user data. The more data available, the better the recommendations. However, collecting and processing this data raises significant privacy concerns. While anonymization is insufficient, existing privacy-preserving methods often compromise recommendation accuracy or completeness. Specifically, matrix factorization, a popular technique for recommendation, involves sensitive user ratings and tuning parameters. This paper tackles the challenge of performing matrix factorization securely, ensuring that user ratings, item preferences, and even the system's internal tuning parameters remain confidential from both the recommendation system itself and any external service providers involved in the computation.
Methods
The core of this work is a novel privacy-preserving matrix factorization protocol built upon fully homomorphic encryption (FHE). Here's a breakdown of their approach:
- Fully Homomorphic Encryption (FHE): The protocol leverages FHE to perform computations directly on encrypted data. This means user ratings are encrypted before being sent to the recommendation system, and all subsequent calculations, including matrix factorization, are done on these encrypted values. The final output (user and item profiles) is also encrypted.
- Addressing FHE Inefficiencies: Standard FHE can be computationally expensive. The authors address two key challenges:
- Inner Product Computation: Matrix factorization heavily relies on inner products of vectors. A naive FHE approach would require one homomorphic multiplication per inner product, which is inefficient. They introduce a novel data structure that allows for multiple operations on encrypted vectors within a single homomorphic operation, significantly reducing computation cost.
- Fixed-Point Arithmetic: Real-number computations in FHE are tricky. They use a fixed-point representation and handle the division-like operations required for this by employing secure two-party computation (2PC) between the recommendation system (RecSys) and a Cryptographic Service Provider (CSP).
- Secure Two-Party Computation (2PC): For certain operations that are too burdensome for FHE alone, they utilize 2PC between the RecSys and the CSP. This allows them to perform computations on encrypted data while ensuring neither party learns the raw inputs.
- Enhancing Privacy of Rated Items: To further protect privacy, they incorporate a mechanism to obfuscate which items a user has rated and the total number of ratings. This is achieved by allowing users to inject fake ratings along with indicator vectors (1 for real, 0 for fake). Crucially, their protocol removes the influence of these fake ratings during the matrix factorization process, thus preserving accuracy.
- Optimized Ciphertext Size: They employ the Chinese Remainder Theorem (CRT) to represent messages in smaller spaces, leading to a linear growth in ciphertext size rather than quadratic, which is a common issue in FHE.
Datasets
The authors evaluated their protocol using the MovieLens 100K dataset. For comparison with prior work, they also used a restricted version of this dataset, focusing on the 40 most popular movies, which resulted in 14,683 ratings.
Key Insights and Ideas
- FHE for Matrix Factorization is Feasible and Practical: The paper demonstrates that FHE, despite its computational overhead, can be practically applied to complex machine learning tasks like matrix factorization for recommendations, achieving a significant speedup over previous cryptographic approaches.
- Novel Data Structure is Key to Efficiency: The introduction of a specialized data structure to exploit the Single Instruction Multiple Data (SIMD) capabilities of FHE is crucial for making the inner product computations efficient. This is a significant algorithmic contribution.
- Hybrid Approach (FHE + 2PC) Balances Security and Performance: Recognizing that FHE alone might not be sufficient for all operations, the authors strategically combine it with 2PC for specific tasks like fixed-point arithmetic, achieving a good balance between privacy guarantees and computational efficiency.
- Obfuscating Rated Items Without Accuracy Loss: The method of injecting fake ratings with indicators, combined with their protocol's ability to filter them out during computation, is a clever way to enhance privacy regarding user item interaction patterns without degrading the quality of recommendations.
- Protecting Tuning Parameters: The ability to keep the recommendation system's internal tuning parameters secret is a valuable addition, as these parameters can reveal business strategies or insights.
Key Results
- Significant Speedup: The proposed protocol runs in approximately 1.5 minutes per iteration on a personal computer, which is dramatically faster than previous FHE-based approaches (e.g., Nikolaenko et al.'s work in CCS 2013, which took about 170 minutes per iteration on more powerful hardware). This represents a speedup of at least 50 times.
- Reduced Communication Cost: The communication overhead is also significantly reduced, with the protocol requiring around 580 MB per iteration for the core matrix factorization, compared to tens of gigabytes in prior work.
- High Accuracy: The relative error in computed profiles is shown to be very small (less than $10^{-4}$) for a sufficient number of bits in the fractional part of the fixed-point representation, indicating that the privacy-preserving approach does not significantly compromise accuracy.
- Scalability: The protocol's complexity is shown to be $O(M/L)$, where M is the number of ratings and L is the number of slots in the FHE ciphertext. Since L is typically in the thousands, this leads to a substantial reduction in computation cost.
- Extended Protocol Performance: The extended protocol, which includes obfuscating rated items, incurs only a linear increase in running time with the number of fake items. For instance, 10% fake ratings take 1.8 minutes and 50% take 2.3 minutes.
Limitations and Future Work
- Error Accumulation: The use of fixed-point arithmetic and the masking/unmasking process can introduce small errors into the computed profiles. While the paper demonstrates these errors are bounded and generally negligible, they are a limitation compared to clear-text computation.
- Computational Overhead: Despite significant improvements, FHE-based computations are still inherently more expensive than computations on unencrypted data. The paper acknowledges that the protocol's performance is still dependent on the efficiency of the underlying FHE scheme.
- Parallelism Potential: The authors suggest that further improvements could be achieved through parallelism, as many FHE operations can be parallelized. They estimate that a parallelized version could be even faster.
- Further Obfuscation Techniques: While they demonstrate how to incorporate fake ratings, they mention that other obfuscation techniques could be applied, suggesting future work in exploring a wider range of privacy-enhancing methods.
Summary updated