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

Mark Zhandry

doi:10.1007/978-3-030-56784-2_22

New techniques for traitor tracing: Size n^1/3 and More from Pairings

Mark Zhandry

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings
Editors	Daniele Micciancio, Thomas Ristenpart
Publisher	Springer
Pages	652-682
Number of pages	31
ISBN (Print)	9783030567835
DOIs	https://doi.org/10.1007/978-3-030-56784-2_22
State	Published - 2020
Event	40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States Duration: Aug 17 2020 → Aug 21 2020

Publication series

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

Conference

Conference	40th Annual International Cryptology Conference, CRYPTO 2020
Country/Territory	United States
City	Santa Barbara
Period	8/17/20 → 8/21/20

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-56784-2_22

Cite this

Zhandry, M. (2020). New techniques for traitor tracing: Size n^1/3 and More from Pairings. In D. Micciancio, & T. Ristenpart (Eds.), Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings (pp. 652-682). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12170 LNCS). Springer. https://doi.org/10.1007/978-3-030-56784-2_22

Zhandry, Mark. / New techniques for traitor tracing : Size n^1/3 and More from Pairings. Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. editor / Daniele Micciancio ; Thomas Ristenpart. Springer, 2020. pp. 652-682 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b08aaa4e2a304eb2b0ce1dc5f08eb6c7,

title = "New techniques for traitor tracing: Size n1/3 and More from Pairings",

abstract = "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.",

author = "Mark Zhandry",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2020.; 40th Annual International Cryptology Conference, CRYPTO 2020 ; Conference date: 17-08-2020 Through 21-08-2020",

year = "2020",

doi = "10.1007/978-3-030-56784-2_22",

language = "English (US)",

isbn = "9783030567835",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "652--682",

editor = "Daniele Micciancio and Thomas Ristenpart",

booktitle = "Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings",

}

Zhandry, M 2020, New techniques for traitor tracing: Size n^1/3 and More from Pairings. in D Micciancio & T Ristenpart (eds), Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12170 LNCS, Springer, pp. 652-682, 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, United States, 8/17/20. https://doi.org/10.1007/978-3-030-56784-2_22

New techniques for traitor tracing: Size n^1/3 and More from Pairings. / Zhandry, Mark.
Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. ed. / Daniele Micciancio; Thomas Ristenpart. Springer, 2020. p. 652-682 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12170 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - New techniques for traitor tracing

T2 - 40th Annual International Cryptology Conference, CRYPTO 2020

AU - Zhandry, Mark

N1 - Publisher Copyright: © International Association for Cryptologic Research 2020.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85089714841&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089714841&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-56784-2_22

DO - 10.1007/978-3-030-56784-2_22

M3 - Conference contribution

AN - SCOPUS:85089714841

SN - 9783030567835

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 652

EP - 682

BT - Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings

A2 - Micciancio, Daniele

A2 - Ristenpart, Thomas

PB - Springer

Y2 - 17 August 2020 through 21 August 2020

ER -

Zhandry M. New techniques for traitor tracing: Size n^1/3 and More from Pairings. In Micciancio D, Ristenpart T, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. Springer. 2020. p. 652-682. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-56784-2_22