Research And Application Of Some Problem On Secure Multi-party Computation

Secure Multi-party Computation (abbreviate as SMC hereinafter) isrefers to solve privacy-preserving collaborative computing between a setof mistrust participants, SMC is required to ensure the independence ofthe input, the correctness of the calculation and don’t let out all the inputvalue to other members at the same time. SMC was first proposed by Yaoin1982, many theoretical research results have been achieved, and manyresearch directions have been produced so far, such as computationalgeometry, data mining, statistical analysis and electronic auction, etc.This dissertation mainly researches on some specialprivacy-preserving secure multi-party comparison problems which arebased on a comprehensive discussion of SMC. The specific work isdivided into the following several aspects:Firstly, we will introduce the theoretical basis of SMC detailedly,summarize the different contributions to SMC which were maken by thepredecessors at different times, expound the research background,significance and the research status of SMC, illustrate the theoreticalknowledge of secure multi-party computation.Secondly, researching on the millionaires’ problem. Millionaires’problem was put forward by professor Yao Qizh who is a ChineseAmerican computer scientist and Turing award winner. In the thirdchapter, at first, we introduce the research progress and some shortages ofexisting protocols, then we propose a millionaires’ comparison protocolwhich is based on Paillier encryption algorithm.Thirdly, researching on the problem of privacy-preserving triangleinequality determination. Triangle inequality determination problem hasimportant application in computational geometry, such asprivacy-preserving triangle constitution determination problem,privacy-preserving triangle shape determination problem andprivacy-preserving vector comparison problem, etc. In this dissertation,based on the research and analysis of this problem, we put forward aprivacy-preserving triangle inequality determination protocol based on Paillier encryption algorithm and a privacy-preserving triangleinequality determination protocol based on scalar product protocol, thenanalyze the security and complexity of the protocols.Finally, researching on the application of SMC, especially in theelectronic auction. The essence of the sealed-bid electronic auction is tochoose the highest price in some bid prices, it is the typical application ofSMC. Based on the analysis of the several existing electronic auction, wedesign a simple and efficient sealed-bid electronic auction scheme.