Research On Secure Multi-Party Computation And Its Extended Problems

The problem of secure multiparty computation is fundamental in the studies of distributed systems, cryptography and practical cryptographic applications. In particular, almost any known cryptographic setting (e.g., encryption, authentication, agreement, signatures, etc.) and any distributed environment (e.g., electronic voting, electronic auctions, private information retrieval, and privacy-preserving data mining, etc.) can be viewed as a special case of this general problem. In the setting of secure multiparty computation, a set of two or more parties with private inputs wish to jointly compute some predetermined function of their inputs. This computation should be such that the outputs received by the parties are distributed according to the function (correctness), and none of the parties learn anything beyond their prescribed output (privacy).In this thesis, several special multi-party computation problems, including mapping comparing problem, data comparing problem and distributed linear algebra problem, are considered. Furthermore, as an extension of secure multi-party computation, the proxy multi-party computation problem is presented. The main contributions of this dissertation are as follows:(1) A new two-party computation problem, the mapping-equivalence problem (determining whether two mappings are equivalent in the sense of privacy-preserving), is proposed. By using the theory of full transformation semigroup as a basic analytic tool and using the determinate-commutative cryptosystem as a basic cryptographic primitive, a secure two-party computation protocol for solving mapping-equivalence problem is constructed on the semi-honest adversary model. Notice that the theory of full transformation semigroup can be used as analytic tool in the constructing of secure computation protocol. Several mathematical conclusions on full transformation semigroup are proved. Specifically, a new family of subsemigroups of the full transformation semigroup, the E-order-preserving transformation semigroups, is presented and the regularity and Green's relations for the finite semigroups in this family is researched. Moreover, as a special case of mapping-equivalence problem, the transformation-equivalence problem (determining whether two transformations are equivalent in the sense of privacy-preserving) is proposed. Two protocols for solving transformation-equivalence problem are constructed based on oblivious transfer and homomorphic encryption scheme, respectively.(2) Both Yao's millionaires'problem (comparing two integers in the sense of privacy-preserving) and extended millionaires'problem (comparing two real numbers in the sense of privacy-preserving) are important secure two-party computation problems. Recently, two symmetric cryptographic solutions are respectively proposed for solving them:by constructing a symmetric cryptographic solution to set-inclusion problem and using it as a basic block, a symmetric cryptographic solution to Yao's millionaires'problem is presented; and by constructing a symmetric cryptographic solution to member determining problem and using it as a building block, a symmetric cryptographic solution to extended millionaires' problem is presented. In this thesis, it is shown that the known symmetric cryptographic solutions to both set-inclusion problem and member determining problem are imperfect (i.e., an execution of such protocol will output a wrong result), which meaning that the known symmetric cryptographic solutions to both Yao's millionaires'problem and extended millionaires'problem are also imperfect (i.e., an execution of such protocol will output a wrong result). Two solutions to set-inclusion problem (thus to Yao's millionaires'problem) and extended millionaires' problem are respectively constructed by using semantically-secure and homomorphic encryption scheme as a basic cryptographic primitive.(3) Two distributed linear algebra problems are considered:(3-1) a new multi-party computation problem, the vectors rank and maximal linearly independent group problem (computing the rank and all maximal linearly independent groups of several vectors in the sense of privacy-preserving) is proposed, and two protocols for solving such problem are constructed based on oblivious transfer and homomorphic encryption scheme, respectively; (3-2) a two-party computation protocol for solving the affine intersection problem (computing the intersection of two affine subspaces on general finite field in the sense of privacy-preserving) is presented based on oblivious transfer as well as homomorphic encryption scheme.(4) As an extension of secure multi-party computation, the proxy multi-party computation (or proxy two-party computation in the case of two parties) problem is presented:in an execution of a secure multi-party computation protocol, the computing capability of each player can be allowed to delegate to some proxy in the sense of privacy-preserving. Some related models of proxy multi-party computation, especially the security-model (in the presence of semi-honest adversaries), are defined. As specific examples, two proxy distributed linear algebra problems are considered:(4-1) an Input(ε)-Output(1) secure proxy multi-party computation protocol for solving the vectors rank and maximal linearly independent group problem is constructed by using the secure multi-party vectors rank and maximal linearly independent group protocol (e.g., the protocol constructed in (3-1)) as a induced protocol, where and |F| is the order of the finite field; (4-2) an Input(ε)-Output(1) secure proxy two-party computation protocol for solving the linear equations common-solution problem (computing the common solutions of two linear equations systems in the sense of privacy-preserving) is proposed by using the secure two-party affine intersection protocol (e.g., the protocol constructed in (3-2)) as a induced protocol, where(5) As a special case of proxy multi-party computation, the common-parameter-used proxy multi-party computation is presented. In such model, all original users of a proxy multi-party computation protocol are allowed to hold (or share) some common parameter(s), which is unknown for any outside third-party. Moreover, two common-parameter-used proxy multi-party computation protocols, one for solving vectors rank and maximal linearly independent group problem and the other for solving linear equations common-solution problem, are constructed.