Study On Secret Comparison And Its Application

Along with the development of the computer network and distributed computing, people needs more information and cooperating calculations with the help of Internet. At the same time, the safety problem is becoming more and more important. Secret comparison is one basic problem of secure multi-party computation, it has great potential prospect in auction, bidding, electronic voting, online business negotiations and some other applications. Secret comparison protocol also can be widely used in all kinds of SMC protocols, solve many related problems as a basis. This thesis mainly studies secret comparison and its applications, researches secure two-party multi-dimensional vector comparison problem, privacy-preserving string equal, string matching, and the minimal circumscribed circle problems.Firstly, this thesis introduces the research background and meaning, describes different comparison problems, and studies the basic knowledge and protocols of SMC, including the concepts of computing model, semi-honest model and secret comparison, introduces the randomized algorithm, and during the basic, protocols, this thesis studies homomorphic encryption, multiplication protocol, scalar product protocol and some classical protocols of secret comparison.Then, the thesis studies some applications of secret comparison, discusses the multi-dimensional vector comparison problem at first, proposes some different protocols based on vector dominance, mult-to-sum and some other basic protocols to solve this problem respectively, analyzes the performance and compares them. This thesis also introduces randomized algorithm, proves its efficiency by theoretical and experimental analysis. After that, this thesis applies private comparison to the string comparison, designs privacy-preserving string equal protocols on the basis of modular exponentiation and homomorphic encryption respectively, and then proposes a string matching protocol based on BMH algorithm.Finally, the thesis discusses computational geometry problems in SMC, mainly studies the minimal circumscribed circle, describes a random algorithm to solve it, and then designs protocols for privacy-preserving minimal circumscribed circle problem in secure multi-party computation.