Realizing Flexible Broadcast Encryption: How to Broadcast to a Public-Key Directory
Realizing Flexible Broadcast Encryption: How to Broadcast to a Public-Key Directory
复制标题
DOI：
10.1145/3576915.3623168
复制
发表时间：
2023-11
期刊：
影响因子：
--
通讯作者：
R. Garg;George Lu;Brent Waters;David J. Wu
中科院分区：
文献类型：
--
作者：
R. Garg;George Lu;Brent Waters;David J. Wu
假设用户想要向K个收件人广播一条加密消息。使用公钥加密，发送方将构建K个不同的密文，每个接收方一个密文。然后，广播消息的大小与K成线性关系。一个自然的问题是，发送者是否能用其大小与接收者的数量成次线性比例的密文来加密消息。广播加密为这个问题提供了一种解决方案，但代价是引入了向不同用户发布密钥的中央可信方(并且相应地，具有解密所有密文的能力)。最近，一些工作引入了分布式广播加密和灵活广播加密等概念，它们将传统公钥加密的分散、不可信任模型与广播加密的效率保证相结合。在灵活的广播加密方案的特定情况下，用户生成他们自己的公钥/私钥，然后可以将他们的公钥发布在任何公钥目录中。随后，用户可以用密文将用户公钥的任意集合加密，密文的大小与广播集合中的公钥的数量成多对数比例。分布式广播加密方案是一种更具限制性的原语，其中每个公钥也与一个索引相关联，并且只能加密到对应于不同索引的一组公钥。在这项工作中，我们介绍了一个通用编译器，它接受任何分布式广播加密方案，并产生一个灵活的广播加密方案。此外，现有的具体有效的分布式广播加密构造具有公钥，其大小随着系统中的最大用户数而变化，而我们得到的灵活的广播加密方案具有如下吸引人的性质：每个公钥的大小随着最大广播集的大小而变化。通过将我们的编译器应用于Kolonelos、Malavolta和Wee(ASIACRYPT 2023)的分布式广播加密方案，我们提供了一种灵活的广播加密方案的实现。在我们的方案中，发送者可以用2KB的密文将128位对称密钥加密给1000多个接收者(来自拥有100万用户的目录)。这比使用标准ElGamal加密对每个用户单独加密小16倍。代价是，与标准ElGamal公钥(32字节)相比，灵活广播加密中的用户公钥(50KB)要大得多。与相似实例化的分布式广播加密方案相比，在不改变密文大小的情况下，用户的公钥长度(50~KB比1.6~MB)减少了32倍。因此，灵活的广播加密提供了一种以较大的个人公钥(相对于普通公钥加密)为代价对发送给大型用户组的消息进行加密的有效方法。
Suppose a user wants to broadcast an encrypted message to K recipients. With public-key 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 \em sublinearly with the number of recipients. Broadcast encryption offers one solution to this problem, but at the cost of introducing a central \em 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 public-key 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 public-key directory. Subsequently, a user can encrypt to an \em 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 concretely-efficient 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 128-bit symmetric key to a set of over 1000 recipients (from a directory with a million users) with a 2~KB ciphertext. This is 16× 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 similarly-instantiated distributed broadcast encryption scheme, we achieve a 32× 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 public-key encryption).