Paper 2020/618
Broadcast Secret-Sharing, 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 Secret-Sharing (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(n-t)/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 n-t. When q = n-t, 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 n-t. 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(n-t)/q)+l-negl(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 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.
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
- 2021-02-10: last of 2 revisions
- 2020-05-26: 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 Secret-Sharing, Bounds and Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/618}, year = {2020}, url = {https://eprint.iacr.org/2020/618} }