【作者】 李敏；

【导师】 周俊；

【作者基本信息】 华东师范大学 ， 工程硕士（专业学位）， 2021， 硕士

【摘要】 聚类分析是数据挖掘和数据分析中的一项主要任务,被广泛应用在生活中,如生物信息处理、模式识别、数字取证、信息检索和目标营销等。近年来云计算迅猛发展,存储/计算能力有限的移动终端设备常常会将大型私有数据集和本地应用(如聚类)发送到云上进行外包存储和外包运算。而现有的云服务器通常是在半可信或恶意的环境下运行,即云尚未可信。因此,如何在聚类的过程中对云端的加密域进行安全高效的代理运算成为了最重要的问题之一。同态加密技术支持在不解密的状态下对密文进行指定运算操作,适合用来解决外包运算的隐私保护问题。K均值聚类是一种经典的聚类算法,由于简洁高效被广泛使用。在现有的同态加密k-means聚类方案中:1)没有有效的方法来处理浮点数外包密文的存储和计算;2)没有有效的方法在不解密的情况下进行密文比较;3)没有最大程度降低客户端的计算开销。为了解决上述问题,本文提出了一个基于POCF的浮点数隐私保护聚类外包计算方案,该方案做出了以下三个方面的贡献:1.针对以往的同态加密k-means聚类算法不支持小数计算的问题,本文的工作着重于研究并提出了一种面向浮点数的同态加密外包计算聚类方案,根据K均值算法的具体步骤设计了三个安全子协议。并且在本文k-means算法上引入了一种安全的浮点数存储办法。2.针对以往的同态加密k-means方案中不支持密文比较的问题,利用支持部分解密的Pailiier算法PCPD子协议中的SEQ安全比较运算和POCF子协议中的SFPC浮点数安全比较运算,设计了一种支持完全密文距离比较的SSD子协议,能够在密文中求解出k个距离中的最小距离。3.针对云服务器的半可信特征,在方案中利用通用可组合UC模型证明了协议的安全性。在四个数据集上对我们的隐私保护聚类算法进行了全面评估,实验数据显示:随着样本数量的增加服务器端的开销占比达到99%以上,云分摊了更多的运算任务,给计算资源匮乏的用户端带来了最小的同态负载。更多还原

【Abstract】 Cluster analysis is a main task in data mining and data analysis.It is widely used in life,such as biological information processing,pattern recognition,digital forensics,information retrieval and target marketing.In recent years,with the rapid development of cloud computing,mobile terminal devices with limited storage /computing capacity often send large private data sets and local applications(such as clustering)to the cloud for outsourcing storage and computing.The existing ECS usually runs in a semi trusted or malicious environment,that is,the cloud is not trusted yet.Therefore,how to perform secure and efficient proxy operation on the encryption domain in the process of clustering has become one of the most important problems.Homomorphic encryption technology supports the specified operation of ciphertext without decryption,which is suitable for solving the privacy protection problem of outsourcing operation.K-means clustering is a classical clustering algorithm,which is widely used because of its simplicity and efficiency.In the existing homomorphic encryption K-means clustering schemes: 1)there is no effective method to deal with the storage and calculation of floating-point outsourcing ciphertext;2)There is no effective method to compare homomorphic ciphertext without decryption;3)It does not minimize the computing overhead of the client.In order to solve the above problems,this thesis proposes a clustering scheme based Privacy-Preserving Outsourced Calculation on Floating Point Numbers,which makes the following three contributions:1.Aiming at the problem that the previous homomorphic encryption K-means clustering algorithm does not support decimal calculation,this thesis focuses on studying and proposing a homomorphic encryption outsourcing computing clustering scheme for floating point numbers,and designs three security sub protocols according to the specific steps of k-means algorithm.In this thesis,a secure floating-point number storage method is introduced into the k-means algorithm.2.Aiming at the problem that the previous homomorphic encryption k-means schemes do not support ciphertext comparison,an SSD sub protocol supporting complete ciphertext distance comparison is designed by using the SEQ security comparison operation in PCPD sub protocol and SFPC floating-point security comparison operation in POCF sub protocol of Paillier algorithm supporting partial decryption,which can solve the minimum distance of k distances in ciphertext.3.According to the semi trusted characteristics of ECS,the security of the protocol is proved by using the UC model.Our privacy protection clustering algorithm is comprehensively evaluated on four data sets.The experimental data show that with the increase of the number of samples,the overhead of the cloud side and computer server side accounts for more than 99%,and the cloud allocates more computing tasks,bringing the smallest homomorphic load to the user side lacking computing resources.更多还原