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

*Rishab Goyal and Willy Quach and 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^\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.

**Category / Keywords: **public-key cryptography / public-key cryptography

**Original Publication**** (with major differences): **IACR-CRYPTO-2019

**Date: **received 2 Jun 2019, last revised 19 Aug 2019

**Contact author: **goyal at utexas edu, quach willy at gmail com, bwaters at cs utexas edu, danwichs at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20190819:212159 (All versions of this report)

**Short URL: **ia.cr/2019/636

[ Cryptology ePrint archive ]