Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty computation (MPC) and, since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that “the product of two secrets is obtained as a linear function of the vector consisting of the coordinate-wise product of two respective share-vectors”. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we abandon the latter linearity condition and instead require that this product is obtained by some, not-necessarily-linear “product reconstruction function”. Is the resulting notion equivalent to multiplicative linear secret sharing? We show the (perhaps somewhat counter-intuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field Fq as the base field Fq over which linear secret sharing is considered. Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players n such that it has t-privacy with t ≈ √ n and such that it does admit a product reconstruction function, yet this function is necessarily nonlinear. Our proof is based on combinatorial arguments involving bilinear forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.
Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty computation (MPC) and, since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that “the product of two secrets is obtained as a linear function of the vector consisting of the coordinate-wise product of two respective share-vectors”. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we abandon the latter linearity condition and instead require that this product is obtained by some, not-necessarily-linear “product reconstruction function”. Is the resulting notion equivalent to multiplicative linear secret sharing? We show the (perhaps somewhat counter-intuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field Fq as the base field Fq over which linear secret sharing is considered. Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players n such that it has t-privacy with t ≈ √ n and such that it does admit a product reconstruction function, yet this function is necessarily nonlinear. Our proof is based on combinatorial arguments involving bilinear forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.
Multiplicative linear secret sharing is a fundamental notion in the area of secure multiparty computation and, since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that the product of two secrets is obtained as a linear function of the vector consisting of the coordinatewise product of two respective share-vectors. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we abandon the latter linearity condition and instead require that this product is obtained by some, not-necessarily-linear “product reconstruction function.” Is the resulting notion equivalent to multiplicative linear secret sharing? We show the (perhaps somewhat counterintuitive) result that this relaxed notion is strictly more general. Concretely, fix a finite field Fq as the base field over which linear secret sharing is considered. Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players n such that it has t-privacy with t=Ω(n) and such that it does admit a product reconstruction function, yet this function is necessarily nonlinear. In addition, we determine the minimum number of players for which those exotic schemes exist. Our proof is based on combinatorial arguments involving quadratic forms. It extends to similar separation results for important variations, such as strongly multiplicative secret sharing.
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.
A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. In the previous work, the following negative result for perfect secret sharing has been shown: The d-multiplicative secret sharing for d players is impossible. This paper extends the impossibility result to non-perfect secret sharing. Our main result is a proof that d-multiplicative secret sharing for d players is impossible even if every player has partial information on the secret (e.g., all but one bit). This result means that there is no need to relax the privacy requirement with leakage of partial information only for the purpose of d-multiplication.
In a data-driven society, individuals and companies encounter numerous situations where private information is an important resource. How can parties handle confidential data if they do not trust everyone involved? This text is the first to present a comprehensive treatment of unconditionally secure techniques for multiparty computation (MPC) and secret sharing. In a secure MPC, each party possesses some private data, while secret sharing provides a way for one party to spread information on a secret such that all parties together hold full information, yet no single party has all the information. The authors present basic feasibility results from the last 30 years, generalizations to arbitrary access structures using linear secret sharing, some recent techniques for efficiency improvements, and a general treatment of the theory of secret sharing, focusing on asymptotic results with interesting applications related to MPC.
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
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...