Paper 2020/618

Broadcast Secret-Sharing, Bounds and Applications

Ivan Damgård, Kasper Green Larsen, and Sophia Yakoubov


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'.

Available format(s)
Publication info
Preprint. MINOR revision.
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
2021-02-10: last of 2 revisions
2020-05-26: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.