Paper 2020/954
New Techniques for Traitor Tracing: Size $N^{1/3}$ and More from Pairings
Mark Zhandry
Abstract
The best existing pairing-based traitor tracing schemes have $O(\sqrt{N})$-sized parameters, which has stood since 2006. This intuitively seems to be consistent with the fact that pairings allow for degree-2 computations, yielding a quadratic compression. In this work, we show that this intuition is false by building a tracing scheme from pairings with $O(\sqrt[3]{N})$-sized parameters. We additionally give schemes with a variety of parameter size trade-offs, including a scheme with constant-size ciphertexts and public keys (but linear-sized secret keys). All of our schemes make black-box use of the pairings. We obtain our schemes by developing a number of new traitor tracing techniques, giving the first significant parameter improvements in pairings-based traitor tracing in over a decade.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A major revision of an IACR publication in CRYPTO 2020
- Keywords
- traitor tracingpairings
- Contact author(s)
- mzhandry @ gmail com
- History
- 2020-09-29: revised
- 2020-08-11: received
- See all versions
- Short URL
- https://ia.cr/2020/954
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/954,
author = {Mark Zhandry},
title = {New Techniques for Traitor Tracing: Size $N^{1/3}$ and More from Pairings},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/954},
year = {2020},
url = {https://eprint.iacr.org/2020/954}
}
