计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (10): 2188-2200.doi: 10.7544/issn1000-1239.2020.20200407
所属专题: 2020密码学与数据隐私保护研究专题
秦红1,王皓1,2,魏晓超1,郑志华1
Qin Hong1, Wang Hao1,2, Wei Xiaochao1, Zheng Zhihua1
摘要: 在多数聚类计算的实际应用中,样本数据通常来自于不同的用户,聚类算法往往需要在用户的联合数据集上进行计算. 而出于隐私保护的目的,用户并不希望与其他参与方共享其私有数据. 因此,如何以隐私保护的方式实现多用户的聚类计算便得到了人们的广泛关注.针对多用户持有数据的场景,研究了k-均值(k-means)聚类算法的安全计算问题,设计了常数轮交互的多用户k-means聚类安全计算协议. 在该协议中,用户使用加法同态加密方案对样本数据加密并上传至独立的辅助计算服务器. 服务器通过与持有私钥的聚类计算方交互,实现了乘法和欧氏距离的安全计算. 此外,基于ABY混合协议框架设计了针对同态密文的最小元素标记协议和除法协议. 协议通过常数轮交互,实现了同态密文、算术分享份额、Yao分享份额之间的相互转换,并利用Yao混乱电路技术实现了对同态密文的最小元素标记以及除法运算,该过程无需使用昂贵的比特分解技术. 在半诚实模型下给出了主协议及所有子协议的安全性证明.
中图分类号: