Research On Multi-Party Computation For Basic Operations

Multi-party computation (MPC) is a basic research area in cryptology. It allows a set of n mutually un-trusted parties to compute a predefined function f with their private information as inputs. After running the MPC protocol, the parties obtain only the predefined outputs but nothing else, and the privacy of their inputs is guaranteed. Generally speaking, any a cryptological protocol can be viewed as a special case of MPC, and thus MPC can be viewed as a general research of cryptological protocols. Generic solutions for MPC (which can compute any function f) already exist, and these generic solutions prove that any multi-party tasks can be carried out securely. However, these solutions tend to be highly inefficient and thus not applicable for practical use. So, to fix this problem, we focus on constructing efficient protocols for specific functions; we will probe into the realization and complexity of some typical basic problems in the MPC setting, and this task is of great importance in theory and application.Although generic solutions for MPC (which can compute any function f) already exist, these solutions tend to be highly inefficient and thus not applicable for practical use. So, to fix this problem, we focus on constructing efficient protocols for specific functions.Generally speaking, the research on MPC can be divided into two settings:MPC in the secret sharing setting and MPC in the threshold homomorphic setting. In the se-cret sharing setting, MPC protocols are based on linear secret sharing schemes (LSSS); the inputs to the protocols and (most of) the intermediate values are shared between the parties. Whereas in the threshold homomorphic setting, MPC protocols are based on (the homomorphic) Paillier public key encryption scheme; the inputs to the protocols and (most of) the intermediate values are encrypted by the Paillier public key encryp- tion scheme and the private key is shared between the parties using a threshold secret sharing scheme. Our work is mainly about MPC in the secret sharing setting and some techniques and ideas in our work can be carried over to the threshold homomorphic set-ting. In the research on MPC in the secret sharing setting, it is often assumed that the underlying secret sharing scheme is built on a prime field Zp, in which p is a prime with bit-lengthι(i.e.ι=[logp]). What's more, for an integer x=(xι-1,…, x1, x0)∈Zp, [x]p is used to denote the sharing of x,and [x]B is used to denote the bitwise sharing of x (namely the sharings of the bits of x). That is to say, we haveOur work is based on an important tool in MPC called bit-decomposition, which is proposed by Damgard et al. in TCC 2006. Given a sharing of secret x, bit-decomposition allows the parties to compute the bitwise sharing of x in constant rounds. That is to say, we have [x]b←Bit-Decomposition([x]p).With the help of bit-decomposition, we can construct protocols for various MPC problems. Specifically, on one hand, with the help of bit-decomposition we can construct protocols for some important boolean operations, such as computing the Hamming-Weight of one shared value, computing the Hamming-Distance or XOR of two shared values, etc; on the other hand, some important and relatively complex arith-metic operation can also be realized relying on bit-decomposition; listed below are 4 main applications of bit-decomposition:●Comparing Shared Values [a]p<[b]p i.e. comparing two shared values a and bTesting the Equality of Shared Values [a]p=[b]p i.e. deciding whether two shared values a and b are equalPublic Modulo Reduction [x mod m]p←Public-Modulo-Reduction([x]p,m)Private Exponentiation [xαmod p]p←Private-Exponentiation([x]p, [a]p)With the help of bit-decomposition, we can get the bitwise sharings of the inputs to these problems, then we will be able to use the "divide and conquer" technique to solve these problems. However, a serious problem is, bit-decomposition is relatively expen-sive. Specifically, the asymptotic communication complexity of bit-decomposition is O(l log l) (l is the bit-length of the input) and thus bit-decomposition is non-linear. Then all the protocols relying on bit-decomposition inherit this inefficiency and the commu-nication complexity of these protocols are also non-linear. In a recent work, Nishide et al. proposed protocols for the first two applications of bit-decomposition, compar-ison and equality test, without relying on bit-decomposition, and the main advantage of their protocols is that the communication complexity is reduced to linear (i.e.O(l)). Then a natural problem is whether a similar conclusion can be arrived at for another two important applications of bit-decomposition:public modulo reduction and private exponentiation. In this paper, we give an answer to this open problem; we show that public modulo reduction and private exponentiation can also be realized without rely- ing on bit-decomposition and the communication complexity can also be reduced to linear.To solve the public modulo reduction problem, we first propose a generaliza-tion of bit-decomposition. This generalization includes two protocols:base-m digit-decomposition and base-m digit-bit-decomposition. Given a sharing of secret x, our base-m digit-decomposition protocol can output the sharings of all the base-m digits of x and our base-m digit-bit-decomposition protocol can output the bitwise sharings of all the base-m digits of x. Our linear public modulo reduction protocol is based on the following simple fact:given the base-m form of an integer x, the value of the least significant base-m digit is just (x mod m). That is to say, to solve the public modulo reduction problem (i.e. computing [x mod m]p from [x]p and m), we need only to ex-tract the sharing of the least significant base-m digit of x; this is just what we do in our linear public modulo reduction protocol without relying on bit-decomposition. Thus our linear public modulo reduction protocol can be viewed as a simplification of the base-m digit-decomposition protocol. What's more, we further generalize the general-ization (of bit-decomposition) above to the hybrid-base case and more importantly, as a simplification of this further generalization, we propose a public modulo reduction protocol with improved efficiency.As for the private exponentiation problem, it is generally believed that this prob-lem can not be solved without relying on bit-decomposition and linear complexity can not be achieved. However, we show that it can. We first propose a protocol to show how to remove the invocation of bit-decomposition (to reduce the communication com-plexity to linear). Then we show a technique to reduce the complexity of this linear protocol significantly. The finally obtained protocol is much more efficient than the existing one.