All known constructions of information theoretic t-out-of-n secret-sharing schemes require secure, private communication channels among the parties for the reconstruction of the secret. We investigate the cost of performing the reconstruction over public communication channels. A naive implementation of this task distributes 2n-2 one times pads to each party. This results in shares whose size is 2n-1 times the secret size. We present three implementations of such schemes that are substantially more efficient. A scheme enabling multiple reconstructions of the secret by different subsets of parties, with factor O(n/t) increase in the shares' size. A one-time scheme, enabling a single reconstruction of the secret, with O(log(n/t)) increase in the shares' size. A one-time scheme, enabling a single reconstruction by a set of size exactly t, with factor O(1) increase in the shares' size. We prove that the first implementation is optimal (up to constant factors) by showing a tight /spl Omega/(n/t) lower bound for the increase in the shares' size.
All known constructions of information theoretic t-out-of-n secret-sharing schemes require secure, private communication channels among the parties for the reconstruction of the secret. We investigate the cost of performing the reconstruction over public communication channels. A naive implementation of this task distributes 2n-2 one times pads to each party. This results in shares whose size is 2n-1 times the secret size. We present three implementations of such schemes that are substantially more efficient. A scheme enabling multiple reconstructions of the secret by different subsets of parties, with factor O(n/t) increase in the shares' size. A one-time scheme, enabling a single reconstruction of the secret, with O(log(n/t)) increase in the shares' size. A one-time scheme, enabling a single reconstruction by a set of size exactly t, with factor O(1) increase in the shares' size. We prove that the first implementation is optimal (up to constant factors) by showing a tight /spl Omega/(n/t) lower bound for the increase in the shares' size.
A secret sharing scheme typically requires secure communications in each of two distribution phases: (1) a dealer distributes shares to participants (share distribution phase); and later (2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to O(log n), where is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.
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
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.
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.
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
Threshold schemes allow secret data to be protected amongst a set of participants in such a way that only a pre-specified threshold of participants can reconstruct the secret from private information (shares) distributed to them on system setup using secure channels. We consider the general problem of designing unconditionally secure threshold schemes whose defining parameters (the threshold and the number of participants) can later be changed by using only public channel broadcast messages. In this paper we are interested in the e#ciency of such threshold schemes, and seek to minimise storage costs (size of shares) as well as optimise performance in low bandwidth environments by minimising the size of necessary broadcast messages. We prove a number of lower bounds on the smallest size of broadcast message necessary to make general changes to the parameters of a threshold scheme in which each participant already holds shares of minimal size.