e realize MPC of multiplication with the setting of N=k,n≥2k-1. We also show that our proposed method is information theoretic secure against a semi-honest adversary.
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.
Secure multi-party computation (MPC) is a cryptographic primitive that lets a num- ber N of mutually distrustful parties compute a function f (x1, . . . , xN ) on their private inputs xi such that at the end of the MPC protocol, each honest party obtains the func- tion’s correct output and no adversary controlling a certain subset of parties learns any- thing about the honest parties’ inputs beyond what can be inferred from the function’s output value. In 2002, [Smi01] and [CGS02] introduced the notion of multi-party quan- tum computation (MPQC) in which arbitrary quantum circuits can be evaluated in a distributed manner, secure against a quantum adversary. Few protocols for MPQC are known. We present a fundamental study of the building blocks of MPC and MPQC in the information-theoretic setting with a focus on protocols built on top of (quantum) se- cret sharing schemes. In particular, we point out structural similarities and differences and compile an extensive list of theoretical feasibility results for the maximum number of corrupted parties within classical and quantum secret sharing and MPC protocols.
Advancements in Internet of Things devices allow for the collection and analysis of big data. Moreover, cloud computing has emerged as an ideal platform for big data analysis because it quickly provides computing resources for analysis at scale. However, concerns exist regarding the privacy and security of this information. Secure computation is a technology that enables computation while maintaining data encryption. In this study, we present a new secure computation based on a client-server model, in which a set of servers perform computations using the inputs of multiple clients. We adopt the(k,n)threshold secret sharing approach, where an inputsis divided intonshares and can be recovered from shares with a thresholdk. However, conventional secure computation using(k,n)threshold secret sharing generally requires the conditionn≥2k−1and communication among multiple servers for each multiplication. To the best of our knowledge, no previous study has solved this problem completely. We demonstrate that processes that require communication can be concentrated in the preprocessing phase and propose a secure computation using(k,n)threshold secret sharing that does not require communication during the secure computation phase, even when multiplication is performed. Moreover, we show that the number of communications does not depend on the number of multiplications, unlike in conventional methods. As communication often requires more processing time than the actual secure computation, our method makes it possible to realize faster overall processing than conventional methods. We also present an extensive security analysis and experimental simulation of the proposed method. Our proposed method achieves information-theoretic security against semi-honest adversaries under certain conditions withn<2k−1.
Abstract. As an extension of multi-party computation (MPC), we propose the concept of secure parallel multi-party computation which is to securely compute multi-functions against an adversary with multistructures. Precisely, there are m functions f1,..., fm and m adversary structures A1,..., Am, where fi is required to be securely computed against an Ai-adversary. We give a general construction to build a parallel multi-party computation protocol from any linear multi-secret sharing scheme (LMSSS), provided that the access structures of the LMSSS allow MPC at all. When computing complicated functions, our protocol has more advantage in communication complexity than the “direct sum” method which actually executes a MPC protocol for each function. The paper also provides an efficient and generic construction to obtain from any LMSSS a multiplicative LMSSS for the same multi-access structure. 1
Secure multiparty computation (MPC) protocols enable n parties, each with private inputs, to compute a given function without leaking information beyond the outputs. One of the main approaches to designing efficient MPC protocols is to use secret sharing. In general, secret sharing based MPC contains three phases: input sharing, circuit evaluation, and output recovery. If the adversary corrupts at most t parties, the protocol typically uses (t,n) threshold secret sharing to share the inputs. In this work, we consider a weaker variant of threshold secret sharing called lazy threshold secret sharing (or simply lazy sharing) and show that: Lazy sharing can serve as a viable alternative to threshold secret sharing in MPC without compromising security. Lazy sharing could be generated more efficiently than threshold secret sharing.