Research On Safe Outsourcing Algorithms For Hermite Normal Form And DBSCAN Clustering

Since Google and Amazon first introduced the concept of “cloud computing” in2006,cloud computing,as a new computing model,has developed rapidly and become an important computing infrastructure.As a basic cloud computing service model,outsourcing computing allows enterprises,organizations and individuals to rent a cloud platform with powerful computing and data storage capabilities to complete local computing tasks,thus greatly reducing the computing burden of users.However,the sensitivity of users' data and the untrustworthiness of cloud servers bring a number of security challenges to this promising computing model.On the one hand,users' data usually contains some private information,once leaked,it may bring huge loss of property to users.On the other hand,out of economic benefits,cloud servers may deliberately obtain and leak users' sensitive information,or even forge calculation results to cheat users.Therefore,how to design a secure and efficient outsourcing algorithm that can protect users' sensitive information and detect the malicious behaviors of cloud servers has important theoretical and application value.This paper studies the secure outsourcing computing problems of Hermite normal form of large-scale matrix and DBSCAN clustering of large-scale data in cloud environment,and proposes two feasible secure and efficient outsourcing algorithms.(1)Hermite normal form(HNF),as a standard form of integer matrix,not only plays a crucial role in solving linear equations with integral coefficients,but also has important applications in many other fields,such as integer programming and lattice-based cryptography.However,the rapid increase of coefficients in the HNF calculation process of the existing algorithms makes the computation very time-consuming.At the same time,the scale of integer matrix that needs to be processed in the practical application is often very large,so it is of great practical significance to study the cloud-assisted HNF computing algorithm.This paper studies the computing problem of HNF in cloud environment,and proposes a secure and efficient outsourcing algorithm for the first time.This algorithm enables resource-constrained clients to securely delegate the heavy task of computing HNF to a resource-rich but untrusted cloud server.By combining random permutation,unimodular matrix transformation and triangular matrix transformation,the paper designs a novel integer matrix encryption method,which not only protects the input/output information of the client,but also detects the deception behavior of the cloud with an optimal probability of 1.In addition,the effectiveness and practicability of the algorithm are verified through rigorous theoretical analysis and a large number of experiments.As the size of the problem increases,so does the cost savings for the client using the designed algorithm.(2)DBSCAN(density-based spatial clustering of applications with noise)algorithm is one of the most popular data clustering analysis technologies.As it does not need to determine the number of clusters in advance and can adaptively find clusters with irregular shapes and noise points,DBSCAN has been widely deployed in various applications of machine learning and artificial intelligence.When users perform large-scale data clustering algorithm,constrained by their limited computing and storage capacities,they can reduce the computing burden by outsourcing their computing tasks to a resource-rich remote cloud server.However,the potential untrustworthiness of the cloud server may bring about many security concerns.To address this problem,this paper designs a privacy-preserving outsourcing algorithm based on honest but curious cloud server model for DBSCAN clustering.The core idea underlying the design is a novel and efficient data encryption technology based on permutation mapping,translation transformation and Householder transformation.By virtue of the good properties of the blinded method,we argue the correctness,security and high efficiency of our algorithm with rigorous theoretical analysis.Also,we comprehensively evaluate the practical performance of the algorithm with extensive experiments.