Fast Secret Computation Using Secret Sharing for n<2k-1 Secure Against Malicious Adversaries

In general, the (k,n)-threshold secret sharing scheme cannot be used to perform an information-theoretically secure secret computation for n<2k-1. Therefore, our research team has been focusing on conditions under which secret computation can be performed securely for n<2k-1, and proposed a secret computation method that is safe against malicious adversaries. However, this method is inefficient because it performs all operations as secret computations. In this paper, we divide the arithmetic operations into precomputations and secret computations and show that we can achieve faster secret computation than the conventional method by concentrating the operations that require communication in precomputation.