Homomorphic Matrix Completion
Homomorphic Matrix Completion
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Xiao-Yang Liu;Zechu Li;Xiaodong Wang
中科院分区：
文献类型：
--
作者：
Xiao-Yang Liu;Zechu Li;Xiaodong Wang
在推荐系统、全球定位、系统识别和移动的社交网络中，服务器从其条目的观察子集完成低秩矩阵是一个基本例程。然而，由于窃听攻击和单点故障问题，将数据发送到云服务器引起了数据隐私问题，例如，网络竞赛在一场隐私诉讼后被取消。本文提出了一种用于隐私保护的同态矩阵完备化算法。首先，我们制定了一个同态矩阵完成问题，服务器上执行密文矩阵完成，并提出了一个加密方案，是快速和易于实现。其次，我们证明了所提出的方案萨蒂斯同态性质，即在密文上解密恢复的矩阵将获得目标矩阵（明文）。第三，我们证明了所提出的方案萨蒂斯（λ，λ）-差分隐私性质。而在相似的隐私保证水平下，我们以更多的样本为代价，将最著名的错误界O（10 pn 31 n2）降低到精确恢复。最后，在合成数据和真实数据上，我们证明了同态核范数最小化和交替最小化算法都能在密文上实现准确的恢复，验证了同态性质。
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 purpose. First, we formulate a 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 homomorphism property that decrypting the recovered matrix on cyphertexts will obtain the target matrix (on plaintexts). Thirdly, we prove that the proposed scheme satisfies an ( ✏ , � ) -differential privacy property. While with similar level of privacy guarantee, we reduce the best-known error bound O ( 10 p n 31 n 2 ) to EXACT recovery at a price of more samples. Finally, on synthetic 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.