An Efficient Single-Key Pirates Tracing Scheme Using Cover-Free Families

Dongvu Tonien; Reihaneh Safavi-Naini

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2006/099

An Efficient Single-Key Pirates Tracing Scheme Using Cover-Free Families

Dongvu Tonien and Reihaneh Safavi-Naini

Abstract

A cover-free family is a well-studied combinatorial structure that has many applications in computer science and cryptography. In this paper, we propose a new public key traitor tracing scheme based on cover-free families. The new traitor tracing scheme is similar to the Boneh-Franklin scheme except that in the Boneh-Franklin scheme, decryption keys are derived from Reed-Solomon codes while in our case they are derived from a cover-free family. This results in much simpler and faster tracing algorithms for single-key pirate decoders, compared to the tracing algorithms of Boneh-Franklin scheme that use Berlekamp-Welch algorithm. Our tracing algorithms never accuse innocent users and identify all traitors with overwhelming probability.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Full version of a paper to appear in ACNS06
Keywords: traitor tracing cover-free family combinatorial cryptography
Contact author(s): dong @ uow edu au
History: 2006-03-28: last of 2 revisions; 2006-03-19: received; See all versions
Short URL: https://ia.cr/2006/099
License: CC BY

BibTeX

@misc{cryptoeprint:2006/099,
      author = {Dongvu Tonien and Reihaneh Safavi-Naini},
      title = {An Efficient Single-Key Pirates Tracing Scheme Using Cover-Free Families},
      howpublished = {Cryptology ePrint Archive, Paper 2006/099},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/099}},
      url = {https://eprint.iacr.org/2006/099}
}