In 2002, Wong-Wang-Wing presented a verifiable redistributing secret shares protocol, where the new parties must have been honest. They used Feldman's Verifiable Secret Sharing scheme, which assumed that the discrete logarithm is hard. In 2013, Nojoumian and Stinson presented information-theoretically (unconditionally) secure schemes under assumption that at most t out of 4t+1 parties are actively corrupt, where only the threshold (but not the number of parties) can be changed. We present an unconditionally secure solution assuming that at most t out of 3t+1 parties are actively corrupt. Our protocol uses properties of the parity-check matrix of a Generalized Reed-Solomon code. Moreover, we introduce a new open problem in the area of Reed-Solomon decoding.
In 2002, Wong-Wang-Wing presented a verifiable redistributing secret shares protocol, where the new parties must have been honest. They used Feldman's Verifiable Secret Sharing scheme, which assumed that the discrete logarithm is hard. In 2013, Nojoumian and Stinson presented information-theoretically (unconditionally) secure schemes under assumption that at most t out of 4t+1 parties are actively corrupt, where only the threshold (but not the number of parties) can be changed. We present an unconditionally secure solution assuming that at most t out of 3t+1 parties are actively corrupt. Our protocol uses properties of the parity-check matrix of a Generalized Reed-Solomon code. Moreover, we introduce a new open problem in the area of Reed-Solomon decoding.
Verifiable secret sharing (VSS) protocols enable parties to share secrets while guaranteeing security (in particular, that all parties hold valid and consistent shares) even if the dealer or some of the participants are malicious. Most work on VSS focuses on the honest majority case, primarily since it enables one to guarantee output delivery (e.g., a corrupted recipient cannot prevent an honest dealer from sharing their value). Feldman's VSS is a well known and popular protocol for this task and relies on the discrete log hardness assumption. In this paper, we present a variant of Feldman's VSS for the dishonest majority setting and formally prove its security. Beyond the basic VSS protocol, we present a publicly-verifiable version, as well as show how to securely add participants to the sharing and how to refresh an existing sharing (all secure in the presence of a dishonest majority). We prove that our protocols are UC secure, for appropriately defined ideal functionalities.
Broadcast and verifiable secret sharing (VSS) are central building blocks for secure multi-party computation. These protocols are required to be resilient against a Byzantine adversary who controls at most t out of the n parties running the protocol. In this dissertation, we consider the design of fault-tolerant protocols for broadcast and verifiable secret sharing with stronger security guarantees and improved round complexity. Broadcast allows a party to send the same message to all parties, and all parties are assured they have received identical messages. Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. We address two important issues related to broadcast: (1) Almost all existing protocols do not distinguish between corrupted parties (who do not follow the protocol) and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly); (2) all existing protocols for broadcast are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. We propose new security models that capture these issues, and present tight feasibility and impossibility results. In the problem of verifiable secret sharing, there is a designated player who shares a secret during an initial sharing phase such that the secret is hidden from an adversary that corrupts at most t parties. In a subsequent reconstruction phase of the protocol, a unique secret, well-defined by the view of honest players in the sharing phase, is reconstructed. The round complexity of VSS protocols is a very important metric of their efficiency. We show two improvements regarding the round complexity of information-theoretic VSS. First, we construct an efficient perfectly secure VSS protocol tolerating t < n/3 corrupted parties that is simultaneously optimal in both the number of rounds and the number of invocations of broadcast. Second, we construct a statistically secure VSS protocol tolerating t < n/2 corrupted parties that has optimal round complexity, and an efficient statistical VSS protocol tolerating t < n/2 corrupted parties that requires one additional round.
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...
In a t-out-of-n robust secret sharing scheme, a secret message is shared among n parties who can reconstruct the message by combining their shares. An adversary can adaptively corrupt up to t of the parties, get their shares, and modify them arbitrarily. The scheme should satisfy privacy, meaning that the adversary cannot learn anything about the shared message, and robustness, meaning that the adversary cannot cause the reconstruction procedure to output an incorrect message. Such schemes are only possible in the case of an honest majority, and here we focus on unconditional security in the maximal corruption setting where n = 2t+ 1. In this scenario, to share an m-bit message with a reconstruction failure probability of at most 2−k, a known lower-bound shows that the share size must be at least m + k bits. On the other hand, all prior constructions have share size that scales linearly with the number of parties n, and the prior state-of-the-art scheme due to Cevallos et al. (EUROCRYPT ’12) achieves m+ Õ(k + n). In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with n = 2t+ 1, that avoids the linear dependence between share size and the number of
In secure multi-party computation n parties jointly evaluate an n-variate function f in the presence of an adversary which can corrupt up till t parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
We prove that a known approach to improve Shamir’s celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for n parties against any collusion of size δn, for any constant δ ∈ (0, 1/2). This result holds in the so-called “non-rushing ” model in which the n shares are submitted simultaneously for reconstruction. We thus finally obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is k(1 + o(1)) +O(κ), where k is the secret length and κ is the security parameter. Like Shamir’s scheme, in this modified scheme any set of more than δn honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on δ) while the number of shares n can grow indepen-dently. In this case, when n is large enough, the scheme satisfies the “threshold ” requirement in an approximate sense; i.e., any set of δn(1 + ρ) honest parties, for arbitrarily small ρ> 0, can efficiently reconstruct the secret. 1