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

IEEE Transactions on Information Theory

Bounds on the Threshold Gap in Secret Sharing and its Applications

Ignacio Cascudo, Ronald Cramer, Chaoping Xing

Published May 21, 2013• 35 citations
Publisher

Abstract

We consider the class of secret sharing schemes where there is no a priori bound on the number of players n but where each of the n share-spaces has fixed cardinality q. We show two fundamental lower bounds on the threshold gap of such schemes. The threshold gap g is defined as r-t, where r is minimal and t is maximal such that the following holds: for a secret with arbitrary a priori distribution, each r-subset of players can reconstruct this secret from their joint shares without error ( r-reconstruction) and the information gain about the secret is nil for each t-subset of players jointly ( t-privacy). Our first bound, which is completely general, implies that if , then g ≥ [( n-t+1)/q] independently of the cardinality of the secret-space. Our second bound pertains to \BBF q-linear schemes with secret-space \BBF qk( k ≥ 2). It improves the first bound when k is large enough. Concretely, it implies that g ≥ [( n-t+1)/ q]+f(q,k,t,n), for some function f that is strictly positive when k is large enough. Moreover, also in the \BBF q-linear case, bounds on the threshold gap independent of t or r are obtained by additionally employing a dualization argument. As an application of our results, we answer an open question about the asymptotics of arithmetic secret sharing schemes and prove that the asymptotic optimal corruption tolerance rate is strictly smaller than 1.

DOI
10.1109/tit.2013.2264504

Related papers

Improved Bounds on the Threshold Gap in Ramp Secret Sharing.

Ignacio Cascudo, Jaron Skovsted Gundersen, Diego Ruano

In this paper, we consider linear secret sharing schemes over a finite field F q , where the secret is a vector in Fℓ q and each of the n shares is a single element of F q . We obtain lower bounds on the so-called threshold gap g of such schemes, defined as the quantity r-t where r is the smallest number such that any subset of r shares uniquely determines the secret and t is the largest number such that any subset of t shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for ℓ ≳ 2 . Furthermore, we also provide bounds, in terms of n and q , on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting.

•Jan 1, 2018•0 citations

Improved Bounds on the Threshold Gap in Ramp Secret Sharing

Ignacio Cascudo, Jaron Skovsted Gundersen, Diego Ruano

In this paper, we consider linear secret sharing schemes over a finite field Fq, where the secret is a vector in Fℓqand each of the n shares is a single element of Fq. We obtain lower bounds on the so-called threshold gap g of such schemes, defined as the quantity r-t where r is the smallest number such that any subset of r shares uniquely determines the secret and t is the largest number such that any subset of t shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for ℓ ≳ 2 . Furthermore, we also provide bounds, in terms of n and q , on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting.

IEEE Transactions on Information Theory•Feb 27, 2019•6 citations

MPC from General Linear Secret-Sharing Schemes

Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen

Introduction In this chapter we will show how the protocols we have seen so far can be generalized to be based on general linear secret-sharing schemes. Doing this generalization has several advantages: first, it allows us to design protocols that protect against general adversary structures, a concept we explain later, and second, it allows us to consider protocols in which the field that is used in defining the secret-sharing scheme can be of size independent of the number of players. This turns out to be an advantage for the applications of multiparty computation (MPC) that we consider later but cannot be done for the protocols that we have seen so far: to use Shamir's scheme for n players based on polynomials as we have seen, the field must be of size at least n +1. For now, we will only consider the theory for linear secret sharing that we need to construct the protocols in this chapter. However, we note already that to get full mileage from the more general applications of secret sharing and MPC, we need additional theory, in particular, about the asymptotic behavior of secret-sharing schemes. This material can be found in Chapter 11. General Adversary Structures The corruption tolerance of the protocols that we have seen so far has been characterized by only a single number t , the maximal number of corruptions that can be tolerated. This is also known as the threshold-t model . One way to motivate this might be to think of corruption of a player as something that requires the adversary to invest some amount of resource, such as time or money. If the adversary has only bounded resources, there should be a limit on the corruptions he or she can do. However, characterizing this limit by only an upper bound implicitly assumes that all players are equally hard to corrupt. In reality, this may be completely false: some players may have much better security than others, so a more realistic model might be that the adversary can corrupt a small number of well-protected players or a large number of poorly protected players. However, the threshold model does not allow us to express this.

Cambridge University Press eBooks•Jun 30, 2015•0 citations

Essentially Optimal Robust Secret Sharing with Maximal Corruptions.

Allison Bishop, Valerio Pastro, Rajmohan Rajaraman +1 more

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

•Jan 1, 2015•2 citations

Communication efficient quantum secret sharing

Kaushik Senthoor, Pradeep Kiran Sarvepalli

A quantum secret sharing scheme is a cryptographic protocol by which a dealer can share a secret among a group of $n$ players so that only certain subsets of players can recover the secret by collaboration. In this paper we propose communication efficient quantum threshold secret sharing schemes. They minimize the amount of quantum communication required to reconstruct the secret when more than the necessary number of players collaborate. They are based on a class of staircase codes proposed by Bitar and El Rouayheb. In a standard $((k,n))$ quantum threshold scheme, any subset of $k$ or more players can recover the secret. The quantum communication cost for reconstruction in such schemes is $k$ qudits for each secret qudit. Using the proposed construction, any subset of $d\ensuremath{\ge}k$ players can also collaborate to recover the secret with a communication cost of $d$ qudits for $d\ensuremath{-}k+1$ secret qudits. In other words, for the proposed schemes the quantum communication cost is only $\frac{d}{d\ensuremath{-}k+1}$ qudits for every secret qudit. For $d>k$, proposed schemes are communication efficient with respect to standard schemes; and when $d=2k\ensuremath{-}1$, the quantum communication cost is reduced by a factor $O(k)$. Further, when $n=2k\ensuremath{-}1$, the proposed schemes have optimal communication cost for secret reconstruction.

arXiv:1801.09500•Physical Review A•Nov 11, 2019•26 citations

Lower Bounds for Leakage-Resilient Secret Sharing.

Jesper Buus Nielsen, Mark Simkin

Threshold secret sharing allows a dealer to split a secret into n shares such that any authorized subset of cardinality at least t of those shares efficiently reveals the secret, while at the same time any unauthorized subset of cardinality less than t contains no information about the secret. Leakage-resilience additionally requires that the secret remains hidden even if one is given a bounded amount of additional leakage from every share.

•Jan 1, 2019•2 citations
We consider the class of secret sharing schemes where there is no a priori bound on the number of players n but where each of the n share-spaces has fixed cardinality q. We show two fundamental lower bounds on the threshold gap of such schemes. The threshold gap g is defined as r-t, where r is minimal and t is maximal such that the following holds: for a secret with arbitrary a priori distribution, each r-subset of players can reconstruct this secret from their joint shares without error ( r-reconstruction) and the information gain about the secret is nil for each t-subset of players jointly ( t-privacy). Our first bound, which is completely general, implies that if , then g ≥ [( n-t+1)/q] independently of the cardinality of the secret-space. Our second bound pertains to \BBF q-linear schemes with secret-space \BBF qk( k ≥ 2). It improves the first bound when k is large enough. Concretely, it implies that g ≥ [( n-t+1)/ q]+f(q,k,t,n), for some function f that is strictly positive when k is large enough. Moreover, also in the \BBF q-linear case, bounds on the threshold gap independent of t or r are obtained by additionally employing a dualization argument. As an application of our results, we answer an open question about the asymptotics of arithmetic secret sharing schemes and prove that the asymptotic optimal corruption tolerance rate is strictly smaller than 1.
In this paper, we consider linear secret sharing schemes over a finite field F q , where the secret is a vector in Fℓ q and each of the n shares is a single element of F q . We obtain lower bounds on the so-called threshold gap g of such schemes, defined as the quantity r-t where r is the smallest number such that any subset of r shares uniquely determines the secret and t is the largest number such that any subset of t shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for ℓ ≳ 2 . Furthermore, we also provide bounds, in terms of n and q , on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting.
In this paper, we consider linear secret sharing schemes over a finite field Fq, where the secret is a vector in Fℓqand each of the n shares is a single element of Fq. We obtain lower bounds on the so-called threshold gap g of such schemes, defined as the quantity r-t where r is the smallest number such that any subset of r shares uniquely determines the secret and t is the largest number such that any subset of t shares provides no information about the secret. Our main result establishes a family of bounds which are tighter than previously known bounds for ℓ ≳ 2 . Furthermore, we also provide bounds, in terms of n and q , on the partial reconstruction and privacy thresholds, a more fine-grained notion that considers the amount of information about the secret that can be contained in a set of shares of a given size. Finally, we compare our lower bounds with known upper bounds in the asymptotic setting.
Introduction In this chapter we will show how the protocols we have seen so far can be generalized to be based on general linear secret-sharing schemes. Doing this generalization has several advantages: first, it allows us to design protocols that protect against general adversary structures, a concept we explain later, and second, it allows us to consider protocols in which the field that is used in defining the secret-sharing scheme can be of size independent of the number of players. This turns out to be an advantage for the applications of multiparty computation (MPC) that we consider later but cannot be done for the protocols that we have seen so far: to use Shamir's scheme for n players based on polynomials as we have seen, the field must be of size at least n +1. For now, we will only consider the theory for linear secret sharing that we need to construct the protocols in this chapter. However, we note already that to get full mileage from the more general applications of secret sharing and MPC, we need additional theory, in particular, about the asymptotic behavior of secret-sharing schemes. This material can be found in Chapter 11. General Adversary Structures The corruption tolerance of the protocols that we have seen so far has been characterized by only a single number t , the maximal number of corruptions that can be tolerated. This is also known as the threshold-t model . One way to motivate this might be to think of corruption of a player as something that requires the adversary to invest some amount of resource, such as time or money. If the adversary has only bounded resources, there should be a limit on the corruptions he or she can do. However, characterizing this limit by only an upper bound implicitly assumes that all players are equally hard to corrupt. In reality, this may be completely false: some players may have much better security than others, so a more realistic model might be that the adversary can corrupt a small number of well-protected players or a large number of poorly protected players. However, the threshold model does not allow us to express this.
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
A quantum secret sharing scheme is a cryptographic protocol by which a dealer can share a secret among a group of nnn players so that only certain subsets of players can recover the secret by collaboration. In this paper we propose communication efficient quantum threshold secret sharing schemes. They minimize the amount of quantum communication required to reconstruct the secret when more than the necessary number of players collaborate. They are based on a class of staircase codes proposed by Bitar and El Rouayheb. In a standard ((k,n))((k,n))((k,n)) quantum threshold scheme, any subset of kkk or more players can recover the secret. The quantum communication cost for reconstruction in such schemes is kkk qudits for each secret qudit. Using the proposed construction, any subset of $d\ensuremath{\ge}k$ players can also collaborate to recover the secret with a communication cost of ddd qudits for $d\ensuremath{-}k+1$ secret qudits. In other words, for the proposed schemes the quantum communication cost is only $\frac{d}{d\ensuremath{-}k+1}$ qudits for every secret qudit. For d>kd>kd>k, proposed schemes are communication efficient with respect to standard schemes; and when $d=2k\ensuremath{-}1$, the quantum communication cost is reduced by a factor O(k)O(k)O(k). Further, when $n=2k\ensuremath{-}1$, the proposed schemes have optimal communication cost for secret reconstruction.