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)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]