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
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 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.
The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphic shared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or secure channels) setting, based on any realizations of these primitives. Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized. Third, note that linear secret sharing schemes can have arbitrary (as opposed to threshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.
We first study the problem of doing Verifiable Secret Sharing (VSS) information theoretically secure for a general access structure. We do it in the model where private channels between players and a broadcast channel is given, and where an active, adaptive adversary can corrupt any set of players not in the access structure. In particular, we consider the complexity of protocols for this problem, as a function of the access structure and the number of players. For all access structures where VSS is possible at all, we show that, up to a polynomial time black-box reduction, the complexity of adaptively secure VSS is the same as that of ordinary secret sharing (SS), where security is only required against a passive, static adversary. Previously, such a connection was only known for linear secret sharing and VSS schemes. We then show an impossibility result indicating that a similar equivalence does not hold for Multiparty Computation (MPC): we show that even if protocols are given blac...
While classically cryptography is concerned with the problem of private communication among two entities, say players, in modern cryptography multi-player protocols play an important role.And among these, it is probably fair to say that secret sharing, and its stronger version verifiable secret sharing (VSS), as well as multi-party computation (MPC) belong to the most appealing and/or useful ones.The former two are basic tools to achieve better robustness of cryptographic schemes against malfunction or misuse by "decentralizing" the security from one single to a whole group of individuals (captured by the term threshold cryptography).The latter allows-at least in principle-to execute any collaboration among a group of players in a secure way that guarantees the correctness of the outcome but simultaneously respects the privacy of the participants.In this work, we study three aspects of secret sharing, VSS and MPC, which we denote by fundamentals, generality, and efficiency.By fundamentals we mean the quest for understanding why a protocol works and is secure in abstract (and hopefully simple) mathematical terms.By generality we mean generality with respect to the underlying mathematical structure, in other words, minimizing the mathematical axioms required to do some task.And efficiency of course deals with the improvement of protocols with respect to some meaningful complexity measure.We briefly summarize our main results.(1) We give a complete characterization of blackbox secret sharing in terms of simple algebraic conditions on the integer sharing coefficients, and we propose a black-box secret sharing scheme with minimal expansion factor.Note that, in contrast to the classical field-based secret sharing schemes, a black-box secret sharing scheme allows to share a secret sampled from an arbitrary Abelian group and requires only black-box access to the group operations and to random group elements.Such a scheme may be very useful in the construction of threshold cryptosystems based on groups with secret order (like RSA).(2) We show that without loss of efficiency, MPC can be based on arbitrary finite rings.This is in sharp contrast to the literature where essentially all MPC protocols require a much stronger mathematical structure, namely a field.Apart from its theoretical value, this can lead to efficiency improvements since it allows a greater freedom in the (mathematical) representation of the task that needs to be securely executed.(3) We propose a unified treatment of perfectly secure linear VSS and distributed commitments (a weaker version of the former), and we show that the security of such a scheme can be reduced to a linear algebra condition.The security of all known schemes follows as corollaries whose proofs are pure linear algebra arguments, in contrast v to some hybrid arguments used in the literature.(4) We construct a new unconditionally secure VSS scheme with minimized reconstruction complexity in the setting of a dishonest minority.This improves on the reconstruction complexity of the previously best known scheme without affecting the (asymptotic) complexity of the sharing phase.In the context of MPC with pre-processing, our scheme allows to improve the computation phase of earlier protocols without increasing the complexity of the pre-processing.(5) Finally, we consider commitment multiplication proofs, which allow to prove a multiplicative relation among three commitments, and which play a crucial role in computationally secure MPC.We study a non-interactive solution which works in a distributed-verifier setting and essentially consists of a few executions of Pedersen's VSS.We simplify and improve the protocol, and we point out a (previously overlooked) property which helps to construct non-interactive proofs of partial knowledge in this setting.This allows for instance to prove the knowledge of ℓ out of m given secrets, without revealing which ones.We also construct a noninteractive distributed-verifier proof of circuit satisfiability, which-in principle-allows to prove anything that can be proven without giving away the proof.
We use a general treatment of both information-theoretic and cryptographic settings for Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme. Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes. First, we expand the construction proposed by Cramer et al. multiplying two different general access structures and we prove some properties of the resulting MSP M. Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et al. gives only multiplicative MPC. Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary). The knowledge of the resulting MSP and the access structure it computes allows us to build an analog of the algebraic simplification protocol of Gennaro et al. We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case, through the application of homomorphic commitments. There is an open problem how efficiently we can determine Γ the access structure of the resulting MSP M. This open problem reflects negatively on the efficiency of the proposed solution.
Recently, several efforts to implement and use an unconditionally secure multi-party computation (MPC) scheme have been put into practice. These implementations are passively secure MPC schemes in which an adversary must follow the MPC schemes. Although passively secure MPC schemes are efficient, passive security has the strong restriction concerning the behavior of the adversary. We investigate how secure we can construct MPC schemes while maintaining comparable efficiency with the passive case, and propose a construction of an actively secure MPC scheme from passively secure ones. Our construction is secure in the t < n/2 setting, which is the same as the passively secure one. Our construction operates not only the theoretical minimal set for computing arbitrary circuits, that is, addition and multiplication, but also high-level operations such as shuffling and sorting. We do not use the broadcast channel in the construction. Therefore, privacy and correctness are achieved but robustness is absent; if the adversary cheats, a protocol may not be finished but anyone can detect the cheat (and may stop the protocol) without leaking secret information. Instead of this, our construction requires O((cBn + n2)κ) communication that is comparable to one of the best known passively secure MPC schemes, O((cMn + n2) log n), where κ denote the security parameter, cB denotes the sum of multiplication gates and high-level operations, and cM denotes the number of multiplication gates. Furthermore, we implemented our construction and confirmed that its efficiency is comparable to the current fastest passively secure implementation.