Cryptology ePrint Archive: Report 2009/532

Building Efficient Fully Collusion-Resilient Traitor Tracing and Revocation Schemes

Sanjam Garg and Abishek Kumarasubramanian and Amit Sahai and Brent Waters

Abstract: In [BSW06,BW06] Boneh et al. presented the first fully collusion-resistant traitor tracing and trace & revoke schemes. These schemes are based on composite order bilinear groups and their security depends on the hardness of the subgroup decision assumption. In this paper we present new, efficient trace & revoke schemes which are based on prime order bilinear groups, and whose security depend on the hardness of the Decisional Linear Assumption or the External Diffie-Hellman (XDH) assumption. This allows our schemes to be flexible and thus much more efficient than existing schemes in terms a variety of parameters including ciphertext size, encryption time, and decryption time. For example, if encryption time was the major parameter of concern, then for the same level of practical security as [BSW06] our scheme encrypts 6 times faster. Decryption is 10 times faster. The ciphertext size in our scheme is 50% less when compared to [BSW06].

We provide the first implementations of efficient fully collusion-resilient traitor tracing and trace & revoke schemes. The ideas used in this paper can be used to make other cryptographic schemes based on composite order bilinear groups efficient as well.

Category / Keywords: Traitor Tracing

Publication Info: CCS 2010 full version

Date: received 2 Nov 2009, last revised 20 Oct 2010

Contact author: sanjamg at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20101020:084858 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]