New traitor tracing schemes using bilinear map

ABSTRACT

Mitsunari et al [15] presented a new traitor tracing scheme which uses Weil pairing in elliptic curves. To the best of our knowledge this is the first scheme that uses bilinear map. The claimed advantage of the scheme is that the ciphertext size is independent of the number of traitors. It is shown that the problem of constructing a pirate key by k colluders is as hard as the so-called "k-weak Diffie-Hellman problem".In this paper, we show an attack on this scheme in which traitors find a linear combination of their keys to construct a pirate key that can be used to decrypt the ciphertext. We identify a class of schemes, that includes MSK, with the property that correct tracing requires the ciphertext size to depend on the collusion threshold. We derive a lower bound on the size of the ciphertext that depends on the number of colluders.We propose a modification to MSK scheme, Scheme 1, which not only ensures constructing a pirate decoder is hard, but also has a number of significant advantages over the initial proposal. In particular, it is a public key traitor tracing scheme while the original scheme is a secret key traitor tracing scheme; it has a black box tracing algorithm while MSK scheme only has an open box tracing algorithm, and finally its security is provable (semantic secure against passive adversary) while there was no security proof for MSK.We also propose two other schemes based on bilinear pairing. Scheme~2, is a generic scheme and can be used with any linear error correcting code. Scheme~3 uses Shamir's secret sharing scheme and has the added property that the encrypted message can be targeted to a subset of users. This is by including user revocation property and allowing selected users to be revoked from the original set of users. We also give proof of security, similar to Scheme 1, and also a tracing algorithm for the two schemes. Finally we give an efficiency comparison for the three schemes against the most efficient schemes with similar security and traceability properties and show that all three schemes are the most efficient ones of their kind.

REFERENCES

• 1: Dan Boneh , Matthew K. Franklin, An Efficient Public Key Traitor Tracing Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.338-353, August 15-19, 1999
• 2: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 3: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 4: D. Boneh and J. Shaw, Collusion-Secure Fingerprinting for Digital Data, IEEE Transactions on Information Theory, 44, No. 5 (1998), pp. 1897--1905.
• 5: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 6: Yevgeniy Dodis , Nelly Fazio, Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.100-115, January 06-08, 2003
• 7: Yevgeniy Dodis , Nelly Fazio , Aggelos Kiayias , Moti Yung, Scalable public-key tracing and revoking, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.190-199, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872062]
• 8: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 9: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 10: Aggelos Kiayias , Moti Yung, Self Protecting Pirates and Black-Box Traitor Tracing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.63-79, August 19-23, 2001
• 11: Aggelos Kiayias , Moti Yung, On Crafty Pirates and Foxy Tracers, Revised Papers from the ACM CCS-8 Workshop on Security and Privacy in Digital Rights Management, p.22-39, November 05, 2001
• 12: Aggelos Kiayias , Moti Yung, Traitor Tracing with Constant Transmission Rate, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.450-465, May 02, 2002
• 13: K. Kurosawa and Y. Desmedt, Optimum Traitor Tracing and Asymmetric Schemes with Arbiter, EuroCrypt'98, LNCS 1403 (1998), pp. 145--157.
• 14: Kaoru Kurosawa , Takuya Yoshida, Linear Code Implies Public-Key Traitor Tracing, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.172-187, February 12-14, 2002
• 15: S. Mitsunari, R. Sakai and M. Kasahara, A New Traitor Tracing, IEICE Trans. Fundamentals, Vol.E85-A, No.2, Feb 2002.
• 16: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000
• 17: P. Paillier, Public-key cryptosystem based on discrete logarithm residues, EuroCrypt'99, LNCS 1592 (1999), pp. 223--238.
• 18: Douglas R. Stinson , R. Wei, Key Preassigned Traceability Schemes for Broadcast Encryption, Proceedings of the Selected Areas in Cryptography, p.144-156, August 17-18, 1998
• 19: Wen-Guey Tzeng , Zhi-Jia Tzeng, A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.207-224, February 13-15, 2001
• 20: Eric R. Verheul, Self-Blindable Credential Certificates from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.533-551, December 09-13, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Security

Keywords:
bilinear map, elliptic curve, revocation, traitor tracing