Broadcast secret-sharing, bounds and applications

TY - GEN

T1 - Broadcast secret-sharing, bounds and applications

AU - Damgård, Ivan Bjerre

AU - Larsen, Kasper Green

AU - Yakoubov, Sophia

N1 - Publisher Copyright: © 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2021/7

Y1 - 2021/7

N2 - Consider a sender S and a group 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 random key with all recipients in A. (The keys shared with different subsets A must be independent.) 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 n−qt l is a lower bound, and we show an upper bound of (n(qt++1)t − t)l, 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 n−qt λ + l − negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes (n(qt++1)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.

AB - Consider a sender S and a group 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 random key with all recipients in A. (The keys shared with different subsets A must be independent.) 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 n−qt l is a lower bound, and we show an upper bound of (n(qt++1)t − t)l, 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 n−qt λ + l − negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes (n(qt++1)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.

KW - Ad-hoc threshold encryption

KW - Secret-sharing

UR - https://www.scopus.com/pages/publications/85115342357

U2 - 10.4230/LIPIcs.ITC.2021.10

DO - 10.4230/LIPIcs.ITC.2021.10

M3 - Article in proceedings

AN - SCOPUS:85115342357

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 2nd Conference on Information-Theoretic Cryptography, ITC 2021

A2 - Tessaro, Stefano

PB - Dagstuhl Publishing

T2 - 2nd Conference on Information-Theoretic Cryptography, ITC 2021

Y2 - 23 July 2021 through 26 July 2021

ER -