Abstract
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 SecretSharing (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 (nt)/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 nt.
When q = nt, 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 nt. 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 (nt)/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 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.
BibTeX  Entry
@InProceedings{damgard_et_al:LIPIcs.ITC.2021.10,
author = {Damg\r{a}rd, Ivan Bjerre and Larsen, Kasper Green and Yakoubov, Sophia},
title = {{Broadcast SecretSharing, Bounds and Applications}},
booktitle = {2nd Conference on InformationTheoretic Cryptography (ITC 2021)},
pages = {10:110:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771979},
ISSN = {18688969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14329},
URN = {urn:nbn:de:0030drops143299},
doi = {10.4230/LIPIcs.ITC.2021.10},
annote = {Keywords: SecretSharing, Adhoc Threshold Encryption}
}
Keywords: 

SecretSharing, Adhoc Threshold Encryption 
Collection: 

2nd Conference on InformationTheoretic Cryptography (ITC 2021) 
Issue Date: 

2021 
Date of publication: 

19.07.2021 