New techniques for traitor tracing: Size n1/3 and More from Pairings

Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


The best existing pairing-based traitor tracing schemes have O(√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 traitor tracing scheme from pairings with O(root 3 of 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). 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings
EditorsDaniele Micciancio, Thomas Ristenpart
Number of pages31
ISBN (Print)9783030567835
StatePublished - 2020
Event40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States
Duration: Aug 17 2020Aug 21 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12170 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference40th Annual International Cryptology Conference, CRYPTO 2020
Country/TerritoryUnited States
CitySanta Barbara

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'New techniques for traitor tracing: Size n1/3 and More from Pairings'. Together they form a unique fingerprint.

Cite this