Paper 2023/1583
Realizing Flexible Broadcast Encryption: How to Broadcast to a PublicKey Directory
Abstract
Suppose a user wants to broadcast an encrypted message to $K$ recipients. With publickey encryption, the sender would construct $K$ different ciphertexts, one for each recipient. The size of the broadcasted message then scales linearly with $K$. A natural question is whether the sender can encrypt the message with a ciphertext whose size scales sublinearly with the number of recipients. Broadcast encryption offers one solution to this problem, but at the cost of introducing a central trusted party who issues keys to different users (and correspondingly, has the ability to decrypt all ciphertexts). Recently, several works have introduced notions like distributed broadcast encryption and flexible broadcast encryption, which combine the decentralized, trustless model of traditional publickey encryption with the efficiency guarantees of broadcast encryption. In the specific case of a flexible broadcast encryption scheme, users generate their own public/private keys and can then post their public key in any publickey directory. Subsequently, a user can encrypt to an arbitrary set of user public keys with a ciphertext whose size scales polylogarithmically with the number of public keys in the broadcast set. A distributed broadcast encryption scheme is a more restrictive primitive where each public key is also associated with an index, and one can only encrypt to a set of public keys corresponding to different indices. In this work, we introduce a generic compiler that takes any distributed broadcast encryption scheme and produces a flexible broadcast encryption scheme. Moreover, whereas existing concretelyefficient constructions of distributed broadcast encryption have public keys whose size scales with the maximum number of users in the system, our resulting flexible broadcast encryption scheme has the appealing property that the size of each public key scales with the size of the maximum broadcast set. We provide an implementation of the flexible broadcast encryption scheme obtained by applying our compiler to the distributed broadcast encryption scheme of Kolonelos, Malavolta, and Wee (ASIACRYPT 2023). With our scheme, a sender can encrypt a 128bit symmetric key to a set of over 1000 recipients (from a directory with a million users) with a 2 KB ciphertext. This is 16$\times$ smaller than separately encrypting to each user using standard ElGamal encryption. The cost is that the user public keys in flexible broadcast encryption are much larger (50 KB) compared to standard ElGamal public keys (32 bytes). Compared to the similarlyinstantiated distributed broadcast encryption scheme, we achieve a 32$\times$ reduction in the user's public key size (50 KB vs. 1.6 MB) without changing the ciphertext size. Thus, flexible broadcast encryption provides an efficient way to encrypt messages to large groups of users at the cost of larger individual public keys (relative to vanilla publickey encryption).
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Major revision. ACM CCS
 Keywords
 broadcast encryptionflexible broadcast encryptiondistributed broadcast encryptionregistrationbased cryptography
 Contact author(s)

rachg96 @ cs utexas edu
gclu @ cs utexas edu
bwaters @ cs utexas edu
dwu4 @ cs utexas edu  History
 20231013: approved
 20231013: received
 See all versions
 Short URL
 https://ia.cr/2023/1583
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1583, author = {Rachit Garg and George Lu and Brent Waters and David J. Wu}, title = {Realizing Flexible Broadcast Encryption: How to Broadcast to a PublicKey Directory}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1583}, year = {2023}, url = {https://eprint.iacr.org/2023/1583} }