Self Protecting Pirates and Black-Box Traitor Tracing

Aggelos Kiayias, Moti Yung

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

Abstract

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
Pages63-79
Number of pages17
ISBN (Electronic)978-3-540-44647-7
ISBN (Print)978-3-540-42456-7
DOIs
Publication statusPublished - 2001

Publication series

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

Fingerprint

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

Cite this