### 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^\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)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2019
Keywords
public-key cryptography
Contact author(s)
goyal @ utexas edu
quach willy @ gmail com
bwaters @ cs utexas edu
danwichs @ gmail com
History
2019-08-19: revised
See all versions
Short URL
https://ia.cr/2019/636

CC BY

BibTeX

@misc{cryptoeprint:2019/636,
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{https://eprint.iacr.org/2019/636}},
url = {https://eprint.iacr.org/2019/636}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.