Study On Several Secure Multi-Party Computation Problems In Different Models

Generally speaking, a secure multi-party computation (SMC) refers to the problem where two or more parties want to jointly compute a function based on their private inputs in a distributed network, and that no more information is revealed to a participant in the computation than can be inferred form that participant's input and output. Secure multi-party computation was firstly brought forward by A.C.Yao in 1982. after five years, Goldreich,Micali and Wigderson presented the secure multi-party computation protocol with cryptography security, which can securely compute an arbitrary function. With the internet development and popularization, it is a important research direction using SMC to solve several special practical fields, such as computational geometry, data mining, set elements, algebra problems and electronic voting. Using the general solution for special cases of multi-party computation can be impractical. In 1998, O.Goldreich pointed out that, special solutions should be developed to solve some special problems.The main research content of this dissertation is as follows, 1. The theory, technique and actuality of Millionaire's problem and Millionaire's extended problem were summarized, including research on Millionaire's problem in the cryptographic communication model and in information theoretic communication model.2. The theory, technique and actuality of algebra problems were summarized, including rank of matrix, solution of algebra equation etc, which adversary model includes semi honest, malicious and covert and communication model includes cryptography and information theory.3. The theory, technique and actuality of privacy preserving set operate protocols were summarized, including privacy preserving set intersection protocol, privacy preserving set pattern matching protocol etc, which adversary model includes semi honest, malicious and covert and communication model includes cryptography and information theory.Correspondingly, the main contributions of this dissertation are as follows:1. We present the extended Millionaires'problem in the information theoretic communication model, which is not only efficient but considering the case of the equality of two numbers.2. We present algebra computation protocol in the semi honest attack model, such as multi-party matrices addition protocol, extended multi-party matrices product protocol and multi-party matrices division protocol etc. using jointed secret randomness technique and secure inversion of field matrices technique, we also present SMC of determinant, SMC of rank and SMC for determining similarity between matrices in the information theoretic model.3. We present whether multi-party sets are jointed, privacy preserving set pattern matching protocol, privacy preserving set intersection cardinality protocol, privacy preserving ser difference protocol and privacy preserving frequency highest element in set-intersection protocol which can against a semi honest adversary in the cryptographic model. We also present privacy preserving set difference protocol and privacy preserving set intersection cardinality protocol which can against a semi honest adversary, privacy preserving set difference and privacy preserving set pattern matching protocol which can against a malicious adversary in the information theoretic model.