Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / traitor tracing, pairings

Original Publication (with major differences): IACR-CRYPTO-2020

Date: received 4 Aug 2020, last revised 29 Sep 2020

Contact author: mzhandry at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200929:201135 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]