Practical Privacy-Preserving K-means Clustering
Published:
关于K-means分类器的隐私保护
本次note是Payman Mohassel1在2020年K-means聚类的隐私保护方案的总结。对于监督学习的安全多方计算有许多方案，比如Secureml,Falcon,GAZELLE和Delphi等。关于非监督学习，比如保护K-means分类器的外包计算2，将MapReduce安全集成到隐私保护协议中，方便在云计算环境中执行。还有比如增加可信或不可信的第三方和用差分隐私保护保护聚类协议。聚类协议中的算法复杂度为$O(n^2 \log n)$，$n$是数据的点数，现如今最常用的聚类算法是贪婪算法，复杂度为$O(n)$。
安全算术乘法
执行最简单的OT协议，Bob持有$T$的序列$(m_{t,1}, \dots, m_{t,N}), \forall t \in [T]$, Alice选择一个值$c \in [N]$。Alice接收$m_{t,c}, \forall [T]$，或者不接收。若Alice为OT接收者，选择$c$并输入，与OT协议的接收者BOB交互通过随机串执行1-out-of-N OT协议。BOB接收到$(k_1, \dots, k_N)$, Alice获得$k_c$。每当BOB收到一个新的第$t$个序列时，他使用$(k_1, \dots, k_N)$作为加密密钥分别加密序列$(m_{t,0}, \dots, m_{t,N}), \forall t \in [T]$, 即$e_{t,i}=Ecn(k_i, m_{t,i}), \forall t \in [T]$，并把结果发送给Alice，之后Alice用解密密钥$k_c$解密密文$e_{t,c}$，并输出$m_{t,c}$. 用固定的OT选择和批量OT协议的结合将带宽需求减少了约一半。比如，若$N=2$，执行$T$次乘法需要$\ell T$个1-out-of-2 OT实例，故需要发送$\ell T (\kappa + \ell)$比特，通过批量OT技术，带宽只需需要$\ell (\kappa + \ell T)$。
安全欧几里得距离
欧式距离计算坐标系中两点之间的直线距离，即各相应坐标差的平方和的平方根。在Kmeans算法中需要计算和比较两点之间的距离。另外，欧式平方距离(ESD)可以代替欧式距离减少计算量。若存在两个点$X$和$Y$，都是$d$维，假设每一方的算术共享是 和，在秘密共享形式下计算两点的距离如下：
[1] Mohassel, Payman, Mike Rosulek, and Ni Trieu. “Practical Privacy-Preserving K-means Clustering” Proc. Priv. Enhancing Technol. 2020, no. 4 (2020): 414-433.
[2] Yuan, Jiawei, and Yifan Tian. “Practical privacy-preserving mapreduce based k-means clustering over large-scale dataset” IEEE transactions on cloud computing 7, no. 2 (2017): 568-579.