Applying General Access Structure to Proactive Secret Sharing Schemes

Svetla Nikova⋆, Ventzislav Nikov, Bart Preneel A, Joos P. L. Vandewalle

Published Jan 1, 2002• 26 citations

Abstract

Verifiable secret sharing schemes (VSS) are secret sharing schemes (SSS) dealing with possible cheating by participants. In this paper we use the VSS proposed by Cramer, Damgard and Maurer [6, 7, 5]. They introduced a purely linear algebraic method to transform monotone span program (MSP) based secret sharing schemes into VSS. In fact, the monotone span program model of Karchmer and Wigderson [14] deals with arbitrary monotone access structures and not just threshold ones. Stinson and Wei [17] proposed a proactive SSS based on threshold (polynomial) VSS. The purpose of this paper is to build unconditionally secure proactive SSS over any access structure, as long as it admits a linear secret sharing scheme (LSSS).

Related papers

Linear VSS and Distributed Commitments Based on Secret Sharing and Pairwise Checks

Serge Fehr, Ueli M. Maurer

Abstract. We present a general treatment of all non-cryptographic (i.e., information-theoretically secure) linear verifiable-secret-sharing (VSS) and distributed-commitment (DC) schemes, based on an underlying secret sharing scheme, pairwise checks between players, complaints, and accusations of the dealer. VSS and DC are main building blocks for unconditional secure multi-party computation protocols. This general approach covers all known linear VSS and DC schemes. The main theorem states that the security of a scheme is equivalent to a pure linear-algebra condition on the linear mappings (e.g. described as matrices and vectors) describing the scheme. The security of all known schemes follows as corollaries whose proofs are pure linear-algebra arguments, in contrast to some hybrid arguments used in the literature. Our approach is demonstrated for the CDM DC scheme, which we generalize to be secure against mixed adversary settings (some curious and some dishonest players), and for the classical BGW VSS scheme, for which we show that some of the checks between players are superfluous, i.e., the scheme is not optimal. More generally, our approach, establishing the minimal conditions for security (and hence the common denominator of the known schemes), can lead to the design of more efficient VSS and DC schemes for general adversary structures. 1

Jan 1, 20024 citations

On the Complexity of Verifiable Secret Sharing and Multi-Party Computation.

Ronald Cramer, Ivan Damgård, Stefan Dziembowski

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...

Jan 1, 20004 citations

On the complexity of verifiable secret sharing and multiparty computation

Ronald Cramer, Ivan Damgård, Stefan Dziembowski

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 hot hold for Multiparty Computation (MPC): we show that even if protocols are given black-box access for free to an idealized secret sharing scheme secure for the access structure in question, it is not possible to handle all relevant access structures efficiently, not even if the adversary is passive and static.In other words, general MPC can only be black-box reduced efficiently to secret sharing if extra properties of the secret sharing scheme used (such as linearity) are assumed.

ACM Symposium on Theory of Computing (STOC)May 1, 200054 citations

Linear Secret Sharing Schemes and Rearrangements of Access Structures

Liang-liangXiao, Mu-lanLiu

In this paper we study linear secret sharing schemes by monotone span programs, according to the relation between realizing access structures by linear secret sharing schemes and computing monotone Boolean functions by monotone span programs. We construct some linear secret sharing schemes. Furthermore, we study the rearrangements of access structures that is very important in practice.

Acta Mathematicae Applicatae Sinica English SeriesJan 1, 20040 citations

On the Power of Nonlinear Secret-Sharing.

Amos Beimel, Yuval Ishai

A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The (monotone) collection of authorized sets is called an access structure, and is freely identified with its characteristic monotone function f : 1}. A family of secret-sharing schemes is called efficient if the total length of the n shares is polynomial in n. Most previously known secret-sharing schemes belonged to a class of linear schemes, whose complexity coincides with the monotone span program size of their access structure. Prior to this work there was no evidence that nonlinear schemes can be significantly more efficient than linear schemes, and in particular there were no candidates for schemes efficiently realizing access structures which do not lie in NC.

Jan 1, 20012 citations

Broadcast (and Round) Efficient Verifiable Secret Sharing ∗

Juan A. Garay, Clint Givens, Rafail Ostrovsky +1 more

Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Because broadcast cannot be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well. We construct a (linear) VSS protocol which uses the broadcast channel only twice in the sharing phase, while running in an overall constant number of rounds. 1

Jan 1, 20130 citations