Paper 2008/384

Improving the Boneh-Franklin Traitor Tracing Scheme

Pascal Junod, Alexandre Karlov, and Arjen K. Lenstra


Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by $k$ traitors out of a static set of $\ell$ legitimate users, then all traitors can be identified given the pirate key. In this paper we address three practicality and security issues of the Boneh-Franklin traitor-tracing scheme. In the first place, without changing the original scheme, we modify its tracing procedure in the non-black-box model such that it allows identification of $k$ traitors in time $\tilde{O}(k^2)$, as opposed to the original tracing complexity $\tilde{O}(\ell)$. This new tracing procedure works independently of the nature of the Reed-Solomon code used to watermark private keys. As a consequence, in applications with billions of users it takes just a few minutes on a common desktop computer to identify large collusions. Secondly, we exhibit the lack of practical value of list-decoding algorithms to identify more than $k$ traitors. Finally, we show that $2k$ traitors can derive the keys of all legitimate users and we propose a fix to this security issue.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Traitor tracing
Contact author(s)
pascal @ junod info
2008-09-14: received
Short URL
Creative Commons Attribution


      author = {Pascal Junod and Alexandre Karlov and Arjen K.  Lenstra},
      title = {Improving the Boneh-Franklin Traitor Tracing Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2008/384},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.