Improving the Round Complexity of Traitor Tracing Schemes

Aggelos Kiayias, Serdar Pehlivanoglu

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


A traitor tracing scheme is a multi user encryption that has a built-in key leakage deterrence mechanism : the sender is capable of utilizing a tracing process that can interact with any adversarial decoder and reveal the identities of the users whose keys are employed by the decoder. A number of desired design goals have been put forth for traitor tracing schemes, notably the minimization of the length of the cipher texts, the length of the encryption key and the storage for private keys. An important efficiency parameter that is not as widely investigated is the round complexity of the tracing process, i.e., the number of rounds of interaction that is required for the tracing process to terminate. In this work we provide (1) a general formalization of this important design consideration, (2) a novel tracing procedure that exhibits an asymptotic improvement over the previously known approaches. Our first result is achieved by casting the tracing process as a game between the tracer and the adversary where the objective of the tracer is to reveal the identity of the corrupted users while the adversary wishes to prevent that while still meeting a minimum functionality requirement. The second result involves a novel application of fingerprinting codes.
Original languageEnglish
Title of host publicationApplied Cryptography and Network Security
Subtitle of host publication8th International Conference, ACNS 2010, Beijing, China, June 22-25, 2010. Proceedings
EditorsJianying Zhou, Moti Yung
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages18
ISBN (Electronic)978-3-642-13708-2
ISBN (Print)978-3-642-13707-5
Publication statusPublished - 2010

Publication series

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


Dive into the research topics of 'Improving the Round Complexity of Traitor Tracing Schemes'. Together they form a unique fingerprint.

Cite this