On Efficient Pairings on Elliptic Curves over Extension Fields

详细信息    查看全文

• 作者：Xusheng Zhang (18) (19)
  Kunpeng Wang (20)
  Dongdai Lin (20)
  
• 关键词：pairing ; elliptic curve over extension field ; multi ; pairing technique
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7708
• 期：1
• 页码：19-34
• 全文大小：296KB
• 参考文献：1. Bailey, D.V., Paar, C.: Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.?1462, pp. 472-85. Springer, Heidelberg (1998) CrossRef
  2. Bailey, D.V., Paar, C.: Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. Journal of Cryptology?14(3), 153-76 (2001)
  3. Bajard, J.C., Imbert, L., Negre, C., Plantard, T.: Efficient multiplication in GF(p^k) for elliptic curve cryptography. In: Proceedings of the 16th IEEE Symposium on Computer Arithmetic 2003, pp. 181-87. IEEE (2003)
  4. Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithms for Pairing-Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.?2442, pp. 354-69. Springer, Heidelberg (2002) CrossRef
  5. Barreto, P.S.L.M., Galbraith, S.D., héigeartaigh, C.ó., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Designs, Codes and Cryptography?42(3), 239-71 (2007) CrossRef
  6. Benger, N., Charlemagne, M., Freeman, D.M.: On the Security of Pairing-Friendly Abelian Varieties over Non-prime Fields. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol.?5671, pp. 52-5. Springer, Heidelberg (2009) CrossRef
  7. Costello, C., Lange, T., Naehrig, M.: Faster Pairing Computations on Curves with High-Degree Twists. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol.?6056, pp. 224-42. Springer, Heidelberg (2010) CrossRef
  8. Costello, C., Stebila, D.: Fixed argument pairings. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol.?6212, pp. 92-08. Springer, Heidelberg (2010) CrossRef
  9. Diem, C.: The GHS attack in odd characteristic. J. Ramanujan Math. Soc.?18(1), 1-2 (2003)
  10. Diem, C.: On the discrete logarithm problem in elliptic curves. Compositio Mathematica?147(01), 75-04 (2011) CrossRef
  11. Estibals, N.: Compact Hardware for Computing the Tate Pairing over 128-Bit-Security Supersingular Curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol.?6487, pp. 397-16. Springer, Heidelberg (2010) CrossRef
  12. Freeman, D., Scott, M., Teske, E.: A Taxonomy of Pairing-Friendly Elliptic Curves. Journal of Cryptology?23(2), 224-80 (2010) CrossRef
  13. Frey, G., Gangl, H.: How to disguise an elliptic curve (Weil descent). In: Talk at ECC 1998, vol.?98 (1998)
  14. Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS Weil Descent Attack. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol.?2332, pp. 29-4. Springer, Heidelberg (2002) CrossRef
  15. Galbraith, S.D., Smart, N.P.: A Cryptographic Application of Weil Descent. In: Walker, M. (ed.) IMA - Crypto & Coding 1999. LNCS, vol.?1746, pp. 191-00. Springer, Heidelberg (1999)
  16. Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. Journal of Symbolic Computation?44(12), 1690-702 (2009) CrossRef
  17. Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. Journal of Cryptology?15(1), 19-6 (2002) CrossRef
  18. Granger, R.: On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.?6477, pp. 283-02. Springer, Heidelberg (2010) CrossRef
  19. Granger, R., Smart, N.P.: On computing products of pairings. Cryptology ePrint Archive Report 2006/172 (2006), Preprint available at ategory-non-proportional">http://eprint.iacr.org/2006/172
  20. Hess, F.: Generalising the GHS attack on the elliptic curve discrete logarithm problem. LMS Journal of Computation and Mathematics?7(1), 167-92 (2004)
  21. Hess, F.: Pairing Lattices. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol.?5209, pp. 18-8. Springer, Heidelberg (2008) CrossRef
  22. Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Trans. on Information Theory?52(10), 4595-602 (2006) CrossRef
  23. Hitt, L.: On the Minimal Embedding Field. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol.?4575, pp. 294-01. Springer, Heidelberg (2007) CrossRef
  24. Joux, A., Vitse, V.: Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on $E(\mathbb{F}_{q^5})$ . Cryptology ePrint Archive, Report 2010/157 (2010), Preprint available at ategory-non-proportional">http://eprint.iacr.org/2010/157
  25. Koblitz, N., Menezes, A.: Pairing-Based Cryptography at High Security Levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol.?3796, pp. 13-6. Springer, Heidelberg (2005) CrossRef
  26. Lee, E., Lee, H.S., Park, C.M.: Efficient and generalized pairing computation on abelian varieties. IEEE Trans. on Information Theory?55(4), 1793-803 (2009) CrossRef
  27. Lim, C.H., Hwang, H.S.: Fast Implementation of Elliptic Curve Arithmetic in GF( / p ^{/ n} ). In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol.?1751, pp. 405-21. Springer, Heidelberg (2000) CrossRef
  28. Menezes, A., Teske, E.: Cryptographic implications of Hess-generalized GHS attack. Applicable Algebra in Engineering, Communication and Computing?16(6), 439-60 (2006) CrossRef
  29. Miller, V.: The Weil pairing, and its efficient calculation. Journal of Cryptology?17(4), 235-61 (2004) CrossRef
  30. Sakemi, Y., Takeuchi, S., Nogami, Y., Morikawa, Y.: Accelerating Twisted Ate Pairing with Frobenius Map, Small Scalar Multiplication, and Multi-pairing. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol.?5984, pp. 47-4. Springer, Heidelberg (2010) CrossRef
  31. Scott, M.: Computing the Tate Pairing. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol.?3376, pp. 293-04. Springer, Heidelberg (2005) CrossRef
  32. Scott, M.: On the Efficient Implementation of Pairing-Based Protocols. In: Chen, L. (ed.) Cryptography and Coding 2011. LNCS, vol.?7089, pp. 296-08. Springer, Heidelberg (2011) CrossRef
  33. Vercauteren, F.: Optimal Pairings. IEEE Trans. on Information Theory?56(1), 455-61 (2010) CrossRef
  34. Zhang, X., Lin, D.: Efficient Pairing Computation on Ordinary Elliptic Curves of Embedding Degree 1 and 2. In: Chen, L. (ed.) IMACC 2011. LNCS, vol.?7089, pp. 309-26. Springer, Heidelberg (2011) CrossRef
  
• 作者单位：Xusheng Zhang (18) (19)
  Kunpeng Wang (20)
  Dongdai Lin (20)
  
  18. Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China
  19. Graduate University of Chinese Academy of Sciences, Beijing, 100049, China
  20. SKLOIS, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100195, China
  
• ISSN：1611-3349

文摘

In implementation of elliptic curve cryptography, three kinds of finite fields have been widely studied, i.e. prime field, binary field and optimal extension field. In pairing-based cryptography, however, pairing-friendly curves are usually chosen among ordinary curves over prime fields and supersingular curves over extension fields with small characteristics. In this paper, we study pairings on elliptic curves over extension fields from the point of view of accelerating the Miller’s algorithm to present further advantage of pairing-friendly curves over extension fields, not relying on the much faster field arithmetic. We propose new pairings on elliptic curves over extension fields can make better use of the multi-pairing technique for the efficient implementation. By using some implementation skills, our new pairings could be implemented much more efficiently than the optimal ate pairing and the optimal twisted ate pairing on elliptic curves over extension fields. At last, we use the similar method to give more efficient pairings on Estibals’s supersingular curves over composite extension fields in parallel implementation.