Efficient Privacy-Preserving Matrix Factorization via Fully Homomorphic Encryption

Sungwook Kim, Jinsu Kim, Dongyoung Koo, Yuna Kim, Hyunsoo Yoon, Jun-Bum Shin

Abstract

Recommendation systems face a "privacy paradox": providing high-quality suggestions requires access to sensitive user data, yet sharing this data exposes users to significant privacy risks. This paper presents a novel privacy-preserving matrix factorization protocol powered by Fully Homomorphic Encryption (FHE). By introducing a specialized data structure that optimizes encrypted vector processing and a hybrid secure two-party computation (2PC) approach, the system achieves a massive performance leap—running iterations in 1.5 minutes compared to the 170 minutes required by previous state-of-the-art methods. The protocol ensures the confidentiality of user ratings, item profiles, and proprietary system parameters while maintaining high recommendation accuracy.

1. Introduction

Modern recommendation engines rely on matrix factorization to predict user preferences. However, traditional implementations require plaintext access to user ratings, which is a major privacy concern. While techniques like Differential Privacy or Garbled Circuits exist, they often compromise accuracy or suffer from prohibitive computational overhead. This work addresses the need for a system that is simultaneously private (hiding ratings and profile shapes), accurate (matching non-private system quality), and efficient enough for practical use.

2. Methodology

The core of the proposed system is Fully Homomorphic Encryption (FHE), which allows mathematical operations on encrypted data without decryption. To overcome the efficiency bottlenecks of FHE in the context of Gradient Descent, the authors introduced several key innovations:

  • Novel Data Structure for SIMD: FHE supports "Single Instruction, Multiple Data" (SIMD), allowing one operation to affect thousands of data slots. The authors designed a specific data packing structure that aligns matrix math with these slots, allowing a single homomorphic operation to process multiple vector operations simultaneously.
  • Secure 2-Party Computation (2PC): Certain operations—like the division and rounding required for fixed-point arithmetic—are extremely "expensive" in FHE. The protocol splits these tasks between the Recommendation System (RecSys) and a Crypto-Service Provider (CSP) using a masked 2PC approach to maintain efficiency without leaking data.
  • Encrypted Indicators: To hide which items a user has rated, the system allows users to submit "fake" ratings. An encrypted indicator vector ensures that only real ratings influence the final model, protecting privacy without distorting results.
System architecture for privacy-preserving matrix factorization involving Users, the Recommendation System (RecSys), and a Crypto-Service Provider (CSP).

3. Experimental Results

The protocol was evaluated using the MovieLens 100K dataset, comparing it against previous benchmarks and testing its scalability with varying levels of privacy obfuscation.

  • Speed: The proposed protocol takes 1.5 minutes per iteration on a standard 6-core PC. In contrast, the previous benchmark took 170 minutes on two 16-core servers. The authors estimate their system is at least 50x faster after normalizing for hardware.
  • Accuracy: The error introduced by fixed-point arithmetic is negligible. With a 20-bit fractional part, the relative error compared to standard floating-point math is less than $10^{-4}$.
  • Scalability: Computation and communication costs grow linearly with the number of ratings divided by the number of FHE slots. Adding 10% fake ratings for privacy only increased runtime from 1.5 to 1.8 minutes.

4. Discussion and Limitations

The "packing" strategy and hybrid cryptographic approach demonstrate that FHE is most powerful when used in conjunction with other secure protocols. By offloading division-like operations to a secure 2-party protocol, the system avoids the multiplicative depth that typically degrades FHE performance.

However, limitations remain. The system requires significant data transfer (580 MB per iteration for 14K ratings), which may pose challenges for scaling to millions of ratings. Furthermore, the current security model assumes "honest-but-curious" participants; adapting the protocol for a "malicious" model where parties might actively cheat would require further research into complex cryptographic proofs.

Summary updated

BibTeX
@inproceedings{kim2016efficient,
  author = {Sungwook Kim and Jinsu Kim and Dongyoung Koo and Yuna Kim and Hyunsoo Yoon and Jun-Bum Shin},
  title = {{Efficient Privacy-Preserving Matrix Factorization via Fully Homomorphic Encryption}},
  booktitle = {Asiaccs},
  year = {2016},
  doi = {10.1145/2897845.2897875},
}
Figure