Paper 2006/099

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

Dongvu Tonien and Reihaneh Safavi-Naini


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Full version of a paper to appear in ACNS06
traitor tracingcover-free familycombinatorial cryptography
Contact author(s)
dong @ uow edu au
2006-03-28: last of 2 revisions
2006-03-19: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.