Privacy-Preserved Approximate Classification Algorithm Based On Homomorphic Encryption

As an important service delivery component in the cloud which utilizes the shared software and hardware resources on cloud servers and provide service to users on demand,more and more people store their data to the cloud server because of the economy and convenience.However,in this computing paradigm,the data privacy of users cannot be guaranteed,and in order to protect the data privacy,users consider to encrypt their own data and then upload it to the cloud server,hence traditional data processing algorithms cannot further process the encrypted data,such as data classifi-cation and retrieval.Therefore,how to meet the two requirements,privacy protection and efficient encrypted computing at the same time,is a key issue which needs to be solved for the current researchThe decision tree classification algorithm has been commonly used in the ma-chine learning domain,and has advantages in performance,scalability,and interpreta-bility.However,in such decision tree classification,there is still problems in the ac-curacy and resistance to data perturbation,when the training data from the real world contains noise.Moreover,these problems make the training model of the cloud server have training error.In this paper,we propose a privacy-preserved ensemble decision tree algorithm based on the homomorphic encryption algorithm.It approximates the user's encrypted data with higher accuracy and stronger robustness in the cloud server.The main work of this thesis includes:(1)We propose a transformation theorem to directly classify the encrypted data which cannot be completed by the previous homomorphic encryption algo-rithm.The proposed algorithm transforms the decision tree model to the polynomial formula,and a strict mathematical proof is given as well.In addi-tion,by reasonably adjusting the calculation order,the proposed algorithm reduces the asymptotic number of times of the ciphertext multiplication from O(n)to O(logn).(2)For the problem that homomorphic ciphertext cannot compared directly,a method using Sigmoid function and Chebyshev approximation is presented,which is inspired by the idea that approximation.Due to less efficiency,a homomorphic approximation classification algorithm is proposed,which is with higher computational efficiency and higher accuracy in decision tree classification.Moreover,we proves the convergence of the proposed algo-rithm through rigorous theoretical derivation,and gives a theoretical ap-proximation error upper bound.(3)In this thesis,we perform experiments on two public datasets,MNIST and Credit.The proposed algorithm is optimized by vertical packing optimization,so that multiple plaintext data is performed once on the ciphertext domain.The experimental results show that the actual approximation error of the proposed algorithm is in line with the theoretical upper bound.Moreover,from the experiment,we can observe that the approximate output of the pro-posed algorithm has better robustness.