Timezone: »

 
Poster
Homomorphic Matrix Completion
Xiao-Yang Liu · Zechu (Steven) Li · Xiaodong Wang

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #923
in Poster Session 1 »
In recommendation systems, global positioning, system identification and mobile social networks, it is a fundamental routine that a server completes a low-rank matrix from an observed subset of its entries. However, sending data to a cloud server raises up the data privacy concern due to eavesdropping attacks and the single-point failure problem, e.g., the Netflix prize contest was canceled after a privacy lawsuit. In this paper, we propose a homomorphic matrix completion algorithm for privacy-preserving data completion. First, we formulate a \textit{homomorphic matrix completion} problem where a server performs matrix completion on cyphertexts, and propose an encryption scheme that is fast and easy to implement. Secondly, we prove that the proposed scheme satisfies the \textit{homomorphism property} that decrypting the recovered matrix on cyphertexts will obtain the target complete matrix in plaintext. Thirdly, we prove that the proposed scheme satisfies an $(\epsilon, \delta)$-differential privacy property. While with similar level of privacy guarantee, we reduce the best-known error bound $O(\sqrt[10]{n_1^3n_2})$ to EXACT recovery at a price of more samples. Finally, on numerical data and real-world data, we show that both homomorphic nuclear-norm minimization and alternating minimization algorithms achieve accurate recoveries on cyphertexts, verifying the homomorphism property.
Keywords: differential privacy · recommendation system · Matrix completion · homomorphic encryption

Author Information

Xiao-Yang Liu (Columbia University)
Zechu (Steven) Li (Columbia University)
Xiaodong Wang (Columbia University)

More from the Same Authors