Self Protecting Pirates and Black-Box Traitor Tracing

Aggelos Kiayias, Moti Yung

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


We present a new generic black-box traitor tracing model in which the pirate-decoder employs a self-protection technique. This mechanism is simple, easy to implement in any (software or hardware) device and is a natural way by which a pirate (an adversary) which is black-box accessible, may try to evade detection. We present a necessary combinatorial condition for black-box traitor tracing of self-protecting devices. We constructively prove that any system that fails this condition, is incapable of tracing pirate-decoders that contain keys based on a superlogarithmic number of traitor keys. We then combine the above condition with specific properties of concrete systems. We show that the Boneh-Franklin (BF) scheme as well as the Kurosawa-Desmedt scheme have no black-box tracing capability in the self-protecting model when the number of traitors is superlogarithmic, unless the ciphertext size is as large as in a trivial system, namely linear in the number of users. This partially settles in the negative the open problem of Boneh and Franklin regarding the general black-box traceability of the BF scheme: at least for the case of superlogarithmic traitors. Our negative result does not apply to the Chor-Fiat-Naor (CFN) scheme (which, in fact, allows tracing in our self-protecting model); this separates CFN black-box traceability from that of BF. We also investigate a weaker form of black-box tracing called single-query “black-box confirmation.” We show that, when suspicion is modeled as a confidence weight (which biases the uniform distribution of traitors), such single-query confirmation is essentially not possible against a self-protecting pirate-decoder that contains keys based on a superlogarithmic number of traitor keys.
Original languageEnglish
Title of host publicationAdvances in Cryptology — CRYPTO 2001
Subtitle of host publication21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings
EditorsJoe Kilian
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages17
ISBN (Electronic)978-3-540-44647-7
ISBN (Print)978-3-540-42456-7
Publication statusPublished - 2001

Publication series

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


Dive into the research topics of 'Self Protecting Pirates and Black-Box Traitor Tracing'. Together they form a unique fingerprint.

Cite this