Software implementation of Tate pairing over GF(2m)

ABSTRACT

Recently, the interest about the Tate pairing over binary fields has decreased due to the existence of efficient attacks to the discrete logarithm problem in the subgroups of such fields. We show that the choice of fields of large size to make these attacks infeasible does not lead to a degradation of the computation performance of the pairing. We describe and evaluate by simulation an implementation of the Tate pairing that allows to achieve good timing results, comparable with those reported in the literature but with a higher level of security.

REFERENCES

• 1: IEEE Standard Specification for Public-Key Cryptography. Technical report, 2000.
• 2: P. Barreto, S. Galbraith, C. hEigeartaigh, and M. Scott. Efficient pairing computation on supersingular abelian varieties. Cryptology ePrint Archives, http://eprint.iacr.org, 2004.
• 3: Paulo S. L. M. Barreto , Hae Yong Kim , Ben Lynn , Michael Scott, Efficient Algorithms for Pairing-Based Cryptosystems, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.354-368, August 18-22, 2002
• 4: 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
• 5: 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
• 6: Don Coppersmith, Evaluating logarithms in GF(2n), Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.201-207, December 1984 [doi>10.1145/800057.808682]
• 7: Steven D. Galbraith , Keith Harrison , David Soldera, Implementing the Tate Pairing, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.324-337, July 07-12, 2002
• 8: P. Gaudry, F. Hess, and N. Smart. Constructive and destructive facets of Weil descent on elliptic curves. Journal of Cryptology, 15:19--46, 2002.
• 9: Darrel Hankerson , Julio López Hernandez , Alfred Menezes, Software Implementation of Elliptic Curve Cryptography over Binary Fields, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.1-24, August 17-18, 2000
• 10: F. Hess. Exponent groups signature schemes and efficient identity based signature schemes based on pairings. Cryptology ePrint Archives http://eprint.iacr.org, 2002.
• 11: 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
• 12: A. K. Lenstra. Contributions Paper on Cryptographic Key Lengths to the Information Security Management Handbook. Harold F. Tipton, 2004.
• 13: N. McCullagh and P. Barreto. Efficient and forward-secure identity-based signcryption. Cryptology ePrint Archives http://eprint.iacr.org, 2004.
• 14: A. Menezes, T. Okamoto, and S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transaction on Information Theory, 39:1639--1646, 1993.
• 15: A M Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.224-314, December 1985, Paris, France
• 16: S. Pohlig and M. Hellman. An improved algorithm for computing logarithm over GF(p) and its cryptographic significance. IEEE Transaction on Information Theory, 24:106--110, 1978.
• 17: J. Pollard. Monte Carlo methods for index computation mod p. Mathematics of Computation, 32:918--924, 1978.
• 18: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 19: N. Smart. An identity based authenticated key agreement protocol based on the Weil pairing. Cryptology ePrint Archives http://eprint.iacr.org, 2001.
• 20: Eric R. Verheul, Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.195-210, May 06-10, 2001