Traitor Tracing with Constant Transmission Rate

Aggelos Kiayias, Moti Yung

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

Abstract / Description of output

An important open problem in the area of Traitor Tracing is designing a scheme with constant expansion of the size of keys (users’ keys and the encryption key) and of the size of ciphertexts with respect to the size of the plaintext. This problem is known from the introduction of Traitor Tracing by Chor, Fiat and Naor. We refer to such schemes as traitor tracing with constant transmission rate. Here we present a general methodology and two protocol constructions that result in the first two public-key traitor tracing schemes with constant transmission rate in settings where plaintexts can be calibrated to be sufficiently large. Our starting point is the notion of “copyrighted function” which was presented by Naccache, Shamir and Stern. We first solve the open problem of discrete-log-based and public-key-based “copyrighted function.” Then, we observe the simple yet crucial relation between (public-key) copyrighted encryption and (public-key) traitor tracing, which we exploit by introducing a generic design paradigm for designing constant transmission rate traitor tracing schemes based on copyrighted encryption functions. Our first scheme achieves the same expansion efficiency as regular ElGamal encryption. The second scheme introduces only a slightly larger (constant) overhead, however, it additionally achieves efficient black-box traitor tracing (against any pirate construction).
Original languageEnglish
Title of host publicationAdvances in Cryptology --- EUROCRYPT 2002
Subtitle of host publicationInternational Conference on the Theory and Applications of Cryptographic Techniques Amsterdam, The Netherlands, April 28 -- May 2, 2002 Proceedings
EditorsLars R. Knudsen
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-540-46035-0
ISBN (Print)978-3-540-43553-2
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Traitor Tracing with Constant Transmission Rate'. Together they form a unique fingerprint.

Cite this