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.
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.
Threshold schemes allow secret data to be protected among a set of participants in such a way that only a prespecified threshold of participants can reconstruct the secret from private information (shares) distributed to them on a 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 efficiency of such threshold schemes, and seek to minimize storage costs (size of shares) as well as optimize performance in low-bandwidth environments by minimizing 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. We establish the tightness of these bounds by demonstrating optimal schemes.
Consider a sender 𝒮 and a group of n recipients. 𝒮 holds a secret message 𝗆 of length l bits and the goal is to allow 𝒮 to create a secret sharing of 𝗆 with privacy threshold t among the recipients, by broadcasting a single message 𝖼 to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset 𝒜 of recipients of size q, 𝒮 may share a random key with all recipients in 𝒜. (The keys shared with different subsets 𝒜 must be independent.) We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q. Our main question is: how large must 𝖼 be, as a function of the parameters? We show that (n-t)/q l is a lower bound, and we show an upper bound of ((n(t+1)/(q+t)) -t)l, matching the lower bound whenever t = 0, or when q = 1 or n-t. When q = n-t, the size of 𝖼 is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires 𝒮 to share a key with every subset of size n-t. We show that this overhead cannot be avoided when 𝖼 has minimal size. We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (n-t)/q λ + l - negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes ((n(t+1))/(q+t) -t)λ + l. BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.
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.
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.
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.
Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.