Paper 2020/618
Broadcast SecretSharing, Bounds and Applications
Ivan Damgård, Kasper Green Larsen, and Sophia Yakoubov
Abstract
Consider a sender S and a group and of n recipients. S holds a secret message m of length l bits and the goal is to allow S to create a secret sharing of m with privacy threshold t among the recipients, by broadcasting a single message c 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 A of recipients of size q, S may share a secret random bit string with all recipients in A. We call this Broadcast SecretSharing (BSS) with parameters l, n, t and q. Our main question is: how large must c be, as a function of the parameters? We show that l(nt)/q is a lower bound, and we show an upper bound of l((n(t+1))/(q+t)t), matching the lower bound whenever t = 0, or when q = 1 or nt. When q = nt, the size of c is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires S to share a key with every subset of size nt. We show that this overhead cannot be avoided when c has minimal size. We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (k(nt)/q)+lnegl(k) (where k is the length of the input to the PRG). The upper bound becomes k((n(t+1))/(q+t)t)+l. BSS can be applied directly to secretkey threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and noninteractive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for noninteractive 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.
Note: Updated Feb 2021. New version has stronger bounds and constructions, and frames things in the context of 'broadcast secret sharing'.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 secret sharingbroadcast secret sharingthreshold encryptionad hoc threshold encryptioninformation theoretic securitylower bounds
 Contact author(s)

sophia yakoubov @ gmail com
ivan @ cs au dk
larsen @ cs au dk  History
 20210210: last of 2 revisions
 20200526: received
 See all versions
 Short URL
 https://ia.cr/2020/618
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/618, author = {Ivan Damgård and Kasper Green Larsen and Sophia Yakoubov}, title = {Broadcast SecretSharing, Bounds and Applications}, howpublished = {Cryptology ePrint Archive, Paper 2020/618}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/618}}, url = {https://eprint.iacr.org/2020/618} }