Paper 2012/531

Generic Construction of Trace and Revoke Schemes

Murat Ak, Aggelos Kiayias, Serdar Pehlivanoglu, and Ali Aydin Selcuk


Broadcast encryption (BE) is a cryptographic primitive that allows a broadcaster to encrypt digital content to a privileged set of users and in this way prevent revoked users from accessing the content. In BE schemes, a group of users, called traitor s may leak their keys and enable an adversary to receive the content. Such malicious users can be detected through traitor tracing (TT) schemes. The ultimate goal in a content distribution system would be combining traitor tracing and broadcast encryption (resulting in a trace and revoke system) so that any receiver key found to be compromised in a tracing process would be revoked from future transmissions. In this paper, we propose a generic method to transform a broadcast encryption scheme into a trace and revoke scheme. This transformation involves the utilization of a fingerprinting code over the underlying BE transmission. While fingerprinting codes have been used for constructing traitor tracing schemes in the past, their usage has various shortcomings such as the increase of the public key size with a linear factor in the length of the code. Instead, we propose a novel way to apply fingerprinting codes that allows for efficient parameters while retaining the traceability property. Our approach is based on a new property of fingerprinting codes we introduce, called public samplability. We have instantiated our generic transformation with the BE schemes of [4, 13, 20] something that enables us to produce trace and revoke schemes with novel properties. Specifically, we show (i) a trace and revoke scheme with constant private key size and short ciphertext size, (ii) the first ID-based trace and revoke scheme, (iii) the first publicly traceable scheme with constant private key size and (iv) the first trace and revoke scheme against pirate rebroadcasting attack in the public key setting.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Digital rights managementbroadcast encryptiontraitor tracingfingerprinting codes.
Contact author(s)
muratak @ cs bilkent edu tr
2013-05-06: revised
2012-09-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Murat Ak and Aggelos Kiayias and Serdar Pehlivanoglu and Ali Aydin Selcuk},
      title = {Generic Construction of Trace and Revoke Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/531},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.