Research On Privacy-Preserving Application Protocol Based On Secure Two-Party Computing

In recent years,the rapid development of new-generation information technologies,such as big data and cloud computing,has not only brought convenience,but also brought security risks.Data leakage have occurred from time to time.It is urgent to achieve data security and protect users' privacy.One of the characteristics of big data is that data is held by different parties.In order to achieve resource sharing,these parties hope to obtain valuable information through cooperation while private data is protected.Secure multi-party computation is a cooperative computing technology,which can securely compute an agreed functionality by multiple parties who don't trust each other.It has been widely used and secure two-party computation is most common.As a special case of secure multi-party computation,secure two-party computation has a wide range of applications and advantages in efficiency.In this thesis,we design privacy-preserving protocols for pattern matching and k-means clustering based on secure two-party computation.The main research include:1.For the case of one party holds wildcard pattern and the other holds text,we propose a privacy-preserving wildcards pattern matching protocol.Using secret sharing and oblivious transfer,we convert wildcards pattern matching to exact pattern matching.Then we call secure string equality test to determine whether the match is successful.With the help of oblivious transfer extension,the computational complexity of our protocol can be reduced to O(?),which ?represents the number of oblivious transfer need to be executed,generally 80 or 128.The communication complexity of our protocol is O(nm),which m,n are the length of pattern and text respectively.We prove that our protocol is secure against semi-honest adversary;2.For the case of cluster calculator use multiple users' data to perform k-means clustering,we research the secure computation of clustering and propose a constant-round two-party protocol by introducing an assisted server.Our protocol can be divided into initialization phase and cluster calculation phase.In the initialization phase,users encrypt data using additive homomorphic encryption(e.g.,paillier)and sends to assisted server.All users don't need to be online during computation.In the cluster calculation phase,the server interacts with cluster calculator which holds secret key to securely compute multiplication,Euclidean distance,number comparison and division.Using homomorphic encryption and ABY,we propose multiplication protocol,distance calculation protocol,minimum element marking protocol and division protocol for homomorphic ciphertext.We achieve mutual conversions of homomorphic ciphertext,arithmetic sharing and Yao sharing.Our protocol doesn't require expensive bit decomposition and has high efficiency.We give formal proof of all protocol in semi-honest adversary model.