Paper 2019/1280

Fast Secrecy Computation with Multiplication Under the Setting of $k\le N<2k-1$ using Secret Sharing Scheme

Keiichi Iwamura and Ahmad Akmal Aminuddin Mohd Kamal

Abstract

In this paper, we describe two new protocols for secure secrecy computation with information theoretical security against the semi-honest adversary and the dishonest majority. Typically, unconditionally secure secrecy computation using the secret sharing scheme is considered impossible under the setting of $n<2k-1$. Therefore, in our previous work, we first took the approach of finding conditions required for secure secrecy computation under the setting of $n<2k-1$ and realized a new technique of conditionally secure secrecy computation. We showed that secrecy computation using a secret sharing scheme can be realized with a semi-honest adversary with the following three preconditions: (1) the value of a secret and a random number used in secrecy multiplication does not include 0; (2) there is a set of shares on 1 that is constructed from random numbers that are unknown to the adversary; and (3) in secrecy computation involving consecutive computation, the position of shares in a set of shares that are handled by each server is fixed. In this paper, we differentiate the relationship between the parameter $n$ of $(k,n)$-threshold secret sharing scheme and N of the number of servers/parties, and realize secrecy computation of multiplication under the setting of $k\le N<2k-1$. In addition, we improve the processing speed of our protocol by dividing the computation process into a Preprocessing Phase and a Computation Phase and shifting the cost for communication to the Preprocessing Phase. This technique allows for information that does not depend on any of the private values, to be generated in advance and significantly reduce the cost of communication in the Computation Phase. For example, for secrecy computation without repetition, the cost for communication can be totally removed in the Computation Phase. As a result, we realize the method for secrecy computation that is faster compared to conventional methods. In addition, our protocols provided solutions for the aforementioned three preconditions and realize secure secrecy computation without any limitation in terms of usability.