In general, the (k, n) threshold secret sharing scheme (SSS) does not allow unconditionally secure multiparty computation (MPC) for n <; 2k - 1 . Therefore, Iwamura research team has been focusing on conditions under which the secure MPC can be performed securely for n <; 2k - 1, and found that their secure MPC protocol for n <; 2k - 1 is allowed under these three conditions against semi-honest adversaries: (1) the secret information does not contain 0 in the secure multiplication; (2) there is a set of distributed values for 1 using random numbers unknown to the adversaries; (3) the position of the values in the set of distributed values handled by each server is fixed during the sequence of computation. However, their protocol is not secure against malicious adversaries while SPDZ, which is representative secure MPC protocol, is secure against malicious adversaries. Therefore, we propose a secure MPC protocol against malicious adversaries based on the protocol of Iwamura research team.
Two-party computation allows two clients to jointly compute an arbitrary function of their inputs without revealing these inputs to each other. In this study, we adopt a server-aided model, in which a set of computing servers performs computation using the inputs of two clients. In the (k, n) threshold secret sharing scheme, input s is divided into n shares and can be recovered from k shares, where k is a threshold. Typically, the multiplication of shares increases the polynomial's degree from (k-1) to (2k-2), thus increasing the number of shares required from k to 2k-1. Because each server typically holds only one share, the number of servers required also increases to 2k-1. Therefore, a set of n servers can compute multiplication securely only if the adversary corrupts at most k-1 <; n/2 servers. In this study, we differentiate N, which is the number of required servers, and n, which is the parameter of the (k, n) threshold secret sharing scheme. We propose a method of multiplication by using only N ≥ k servers. This is implemented by sending two shares of the same input to each server. In a “normal” method, sending multiple shares to one server violates security because k shares can be leaked from k-1 servers. We overcome this by implementing a different functionality, where each share is first encrypted with a different random number (encrypted share) before being sent to a server. Instead of the “normal shares” of ab, our protocol computes the encrypted shares of ab using the encrypted shares of a and b. We show that the proposed method is secure against a non-colluding semi-honest adversary. Moreover, we implement our method in MATLAB and show its efficiency.
In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by
k2k−1⋅H(s), where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a
L1 fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of
kL2k−1⋅H(s), under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely
k2k−2+1/L⋅H(s), which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.