Paper 2016/232

Efficient Privacy-Preserving Matrix Factorization via Fully Homomorphic Encryption

Sungwook Kim, Jinsu Kim, Dongyoung Koo, Yuna Kim, Hyunsoo Yoon, and Junbum Shin

Abstract

Recommendation systems become popular in our daily life. It is well known that the more the release of users’ personal data, the better the quality of recommendation. However, such services raise serious privacy concerns for users. In this paper, focusing on matrix factorization-based recommendation systems, we propose the first privacy-preserving matrix factorization using fully homomorphic encryption. On inputs of encrypted users' ratings, our protocol performs matrix factorization over the encrypted data and returns encrypted outputs so that the recommendation system knows nothing on rating values and resulting user/item profiles. It provides a way to obfuscate the number and list of items a user rated without harming the accuracy of recommendation, and additionally protects recommender's tuning parameters for business benefit and allows the recommender to optimize the parameters for quality of service. To overcome performance degradation caused by the use of fully homomorphic encryption, we introduce a novel data structure to perform computations over encrypted vectors, which are essential operations for matrix factorization, through secure 2-party computation in part. With the data structure, the proposed protocol requires dozens of times less computation cost over those of previous works. Our experiments on a personal computer with 3.4 GHz 6-cores 64 GB RAM show that the proposed protocol runs in 1.5 minutes per iteration. It is more efficient than Nikolaenko et al.'s work proposed in CCS 2013, in which it took about 170 minutes on two servers with 1.9 GHz 16-cores 128 GB RAM.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ASIACCS 2016
Keywords
homomorphic encryptionmatrix factorizationgradient descentprivacy
Contact author(s)
kim sungwook0630 @ gmail com
History
2016-03-03: received
Short URL
https://ia.cr/2016/232
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/232,
      author = {Sungwook Kim and Jinsu Kim and Dongyoung Koo and Yuna Kim and Hyunsoo Yoon and Junbum Shin},
      title = {Efficient Privacy-Preserving Matrix Factorization via Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2016/232},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/232}},
      url = {https://eprint.iacr.org/2016/232}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.