Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Essentially Optimal Robust Secret Sharing with Maximal Corruptions.

Allison Bishop, Valerio Pastro, Rajmohan Rajaraman, Daniel Wichs

Published Jan 1, 2015• 2 citations
OpenAlex

Abstract

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

Related papers

Nearly Optimal Robust Secret Sharing against Rushing Adversaries.

Pasin Manurangsi, Akshayaram Srinivasan, Prashant Nalini Vasudevan

Robust secret sharing is a strengthening of standard secret sharing that allows the shared secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the n shares, the adversary is allowed to adaptively corrupt and modify up to t shares, where \(n = 2t+1\) (Note that if the adversary is allowed to modify any more shares, then correct reconstruction would be impossible.). Further, we deal with rushing adversaries, meaning that the adversary is allowed to see the honest parties’ shares before modifying its own shares.

•Jan 1, 2019•1 citation

Nearly optimal robust secret sharing

Mahdi Cheraghchi

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 “nonrushing” model in which the n shares are submitted simultaneously for reconstruction. We thus finally obtain a simple, 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 independently. 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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•10 citations

Nearly Optimal Robust Secret Sharing.

Mahdi Cheraghchi

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

•Jan 1, 2015•3 citations

Leakage-Resilient Secret Sharing Against Colluding Parties

Ashutosh Kumar, Raghu Meka, Amit Sahai

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.

Annual Symposium on Foundations of Computer Science•Nov 1, 2019•34 citations

Unconditionally-secure ideal robust secret sharing schemes for threshold and multilevel access structure

Mahabir Prasad Jhanwar, Reihaneh Safavi–Naini

Abstract. An n -player -secure robust secret sharing scheme is a ( t , n )-threshold secret sharing scheme with the additional property that the secret can be recovered, with probability at least , from the set of all shares even if up to t players provide incorrect shares. The existing constructions of robust secret sharing schemes for the range have the share size larger than the secret size. An important goal in this area is to minimize the share size. In the paper, we propose a new unconditionally-secure robust secret sharing scheme for the case with share size equal to the secret size. This is the minimum possible size as dictated by the perfect secrecy of the scheme. We further extend our scheme to realize a class of multilevel access structures that satisfy a special condition. The property that the share size is equal to secret size is preserved in the extended scheme. The proposed scheme is the first known robust secret sharing scheme realizing multilevel access structure.

Journal of Mathematical Cryptology•Oct 8, 2013•2 citations

Broadcast and verifiable secret sharing: new security models and round optimal constructions

Jonathan I. Katz, Ranjit Kumaresan

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.

•Jan 1, 2012•1 citation
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
Robust secret sharing is a strengthening of standard secret sharing that allows the shared secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the n shares, the adversary is allowed to adaptively corrupt and modify up to t shares, where n=2t+1n = 2t+1n=2t+1 (Note that if the adversary is allowed to modify any more shares, then correct reconstruction would be impossible.). Further, we deal with rushing adversaries, meaning that the adversary is allowed to see the honest parties’ shares before modifying its own shares.
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 “nonrushing” model in which the n shares are submitted simultaneously for reconstruction. We thus finally obtain a simple, 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 independently. 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.
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
In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.
Abstract. An n -player -secure robust secret sharing scheme is a ( t , n )-threshold secret sharing scheme with the additional property that the secret can be recovered, with probability at least , from the set of all shares even if up to t players provide incorrect shares. The existing constructions of robust secret sharing schemes for the range have the share size larger than the secret size. An important goal in this area is to minimize the share size. In the paper, we propose a new unconditionally-secure robust secret sharing scheme for the case with share size equal to the secret size. This is the minimum possible size as dictated by the perfect secrecy of the scheme. We further extend our scheme to realize a class of multilevel access structures that satisfy a special condition. The property that the share size is equal to secret size is preserved in the extended scheme. The proposed scheme is the first known robust secret sharing scheme realizing multilevel access structure.
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.