Paper 2019/636

Broadcast and Trace with N^epsilon Ciphertext Size from Standard Assumptions

Rishab Goyal, Willy Quach, Brent Waters, and Daniel Wichs

Abstract

We construct a broadcast and trace scheme (also known as trace and revoke or broadcast, trace and revoke) with $N$ users, where the ciphertext size can be made as low as $O(N^{ϵ})$, for any arbitrarily small constant $ϵ>0$. This improves on the prior best construction of broadcast and trace under standard assumptions by Boneh and Waters (CCS `06), which had ciphertext size $$. While that construction relied on bilinear maps, ours uses a combination of the learning with errors (LWE) assumption and bilinear maps. Recall that, in both broadcast encryption and traitor-tracing schemes, there is a collection of $$ users, each of which gets a different secret key $$. In broadcast encryption, it is possible to create ciphertexts targeted to a subset $$ of the users such that only those users can decrypt it correctly. In a traitor tracing scheme, if a subset of users gets together and creates a decoder box $$ that is capable of decrypting ciphertexts, then it is possible to trace at least one of the users responsible for creating $$. A broadcast and trace scheme intertwines the two properties, in a way that results in more than just their union. In particular, it ensures that if a decoder $$ is able to decrypt ciphertexts targeted toward a set $$ of users, then it should be possible to trace one of the users in the set $$ responsible for creating $$, even if other users outside of $$ also participated. As of recently, we have essentially optimal broadcast encryption (Boneh, Gentry, Waters CRYPTO `05) under bilinear maps and traitor tracing (Goyal, Koppula, Waters STOC `18) under LWE, where the ciphertext size is at most poly-logarithmic in $$. The main contribution of our paper is to carefully combine LWE and bilinear-map based components, and get them to interact with each other, to achieve broadcast and trace.