Paper 2019/636

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

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


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^\epsilon)$, for any arbitrarily small constant $\epsilon>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 $O(N^{1/2})$. 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 $N$ users, each of which gets a different secret key $\textrm{sk}_i$. In broadcast encryption, it is possible to create ciphertexts targeted to a subset $S \subseteq [N]$ 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 $D$ that is capable of decrypting ciphertexts, then it is possible to trace at least one of the users responsible for creating $D$. 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 $D$ is able to decrypt ciphertexts targeted toward a set $S$ of users, then it should be possible to trace one of the users in the set $S$ responsible for creating $D$, even if other users outside of $S$ 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 $N$. 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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2019
public-key cryptography
Contact author(s)
goyal @ utexas edu
quach willy @ gmail com
bwaters @ cs utexas edu
danwichs @ gmail com
2019-08-19: revised
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Willy Quach and Brent Waters and Daniel Wichs},
      title = {Broadcast and Trace with N^epsilon Ciphertext Size from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/636},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.