International Association for Cryptologic Research

International Association
for Cryptologic Research


Broadcast and Trace with $N^{\varepsilon }$ Ciphertext Size from Standard Assumptions

Rishab Goyal
Willy Quach
Brent Waters
Daniel Wichs
DOI: 10.1007/978-3-030-26954-8_27 (login may be required)
Search ePrint
Search Google
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^\varepsilon )$$ , for any arbitrarily small constant $$\varepsilon >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 $${\mathsf {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.
Video from CRYPTO 2019
  title={Broadcast and Trace with 
$$N^{\varepsilon }$$
 Ciphertext Size from Standard Assumptions},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  author={Rishab Goyal and Willy Quach and Brent Waters and Daniel Wichs},