摘要：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.
