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.
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 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.
There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes forn-party access structures; consistent with our current knowledge the optimal share size can be anywhere between polynomial and exponential inn. For linear secret-sharing schemes, the share size for almost alln-party access structures is exponential inn. We would like to study larger classes of secret-sharing schemes with two goals: 1) prove lower bounds for larger classes of secret-sharing schemes; and 2) construct efficient secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC’20) introduced a new class of secret-sharing schemes in which the shares are generated by applying degree-dpolynomials to the secret and some random field elements. We define and study two additional classes of polynomial secret-sharing schemes: 1) schemes in which the reconstruction of the secret is done using polynomials; and 2) schemes in which both sharing and reconstruction are done by polynomials. Our main result is a construction of secret-sharing schemes and conditional disclosure of secrets protocols with quadratic sharing and reconstruction that are more efficient than linear secret-sharing schemes. To complement our results, we prove lower bounds on the share size for schemes with polynomial reconstruction. Finally, we give an evidence that schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction.