Speeding Up Ate Pairing Computation in Affine Coordinates

详细信息    查看全文

• 作者：Duc-Phong Le (19)
  Chik How Tan (19)
  
• 关键词：Ate pairing ; Pairing computation ; final exponentiation ; affine coordinates ; cubic twisted curves ; pairing ; friendly elliptic curves
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7839
• 期：1
• 页码：278-292
• 全文大小：287KB
• 参考文献：1. Aranha, D.F., Karabina, K., Longa, P., Gebotys, C.H., López, J.: Faster explicit formulas for computing pairings over ordinary curves. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.?6632, pp. 48-8. Springer, Heidelberg (2011) CrossRef
  2. 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-68. Springer, Heidelberg (2002) CrossRef
  3. Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol.?3006, pp. 17-5. Springer, Heidelberg (2004) CrossRef
  4. Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol.?3897, pp. 319-31. Springer, Heidelberg (2006) CrossRef
  5. Beuchat, J.-L., González-Díaz, J.E., Mitsunari, S., Okamoto, E., Rodríguez-Henríquez, F., Teruya, T.: High-speed software implementation of the optimal Ate pairing over barreto-naehrig curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol.?6487, pp. 21-9. Springer, Heidelberg (2010) CrossRef
  6. Blake, I.F., Murty, V.K., Xu, G.: Refinements of Miller’s algorithm for computing the Weil/Tate pairing. J. Algorithms?58(2), 134-49 (2006) CrossRef
  7. Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.?2139, pp. 213-29. Springer, Heidelberg (2001) CrossRef
  8. Boxall, J., El Mrabet, N., Laguillaumie, F., Le, D.-P.: A variant of miller’s formula and algorithm. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol.?6487, pp. 417-34. Springer, Heidelberg (2010) CrossRef
  9. Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptography?37, 133-41 (2005) CrossRef
  10. Costello, C., Boyd, C., González Nieto, J.M., Wong, K.K.-H.: Avoiding full extension field arithmetic in pairing computations. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol.?6055, pp. 203-24. Springer, Heidelberg (2010) CrossRef
  11. 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
  12. El Mrabet, N., Guillermin, N., Ionica, S.: A study of pairing computation for elliptic curves with embedding degree 15. Cryptology ePrint Archive, Report 2009/370 (2009), ategory-non-proportional">http://eprint.iacr.org/
  13. Freeman, D., Scott, M., Teske, E.: A Taxonomy of Pairing-Friendly Elliptic Curves. J. Cryptol.?23, 224-80 (2010) CrossRef
  14. Galbraith, S.D., Harrison, K., Soldera, D.: Implementing the tate pairing. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol.?2369, pp. 324-37. Springer, Heidelberg (2002) CrossRef
  15. Granger, R., Scott, M.: Faster squaring in the cyclotomic subgroup of sixth degree extensions. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol.?6056, pp. 209-23. Springer, Heidelberg (2010) CrossRef
  16. Hess, F., Smart, N.P., Vercauteren, F.: The eta pairing revisited. IEEE Transactions on Information Theory?52, 4595-602 (2006) CrossRef
  17. Joux, A.: A One Round Protocol for Tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS-IV. LNCS, vol.?1838, pp. 385-94. Springer, Heidelberg (2000)
  18. Kachisa, E.J., Schaefer, E.F., Scott, M.: Constructing Brezing-Weng Pairing-Friendly Elliptic Curves Using Elements in the Cyclotomic Field. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol.?5209, pp. 126-35. Springer, Heidelberg (2008) CrossRef
  19. Karabina, K.: Squaring in cyclotomic subgroups. Cryptology ePrint Archive, Report 2010/542 (2010), ategory-non-proportional">http://eprint.iacr.org/
  20. Kobayashi, T., Aoki, K., Imai, H.: Efficient algorithms for tate pairing. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.?E89-A(1), 134-43 (2006) CrossRef
  21. Kobayashi, T., Morita, H., Kobayashi, K., Hoshino, F.: Fast elliptic curve algorithm combining frobenius map and table reference to adapt to higher characteristic. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.?1592, pp. 176-89. Springer, Heidelberg (1999) CrossRef
  22. Lauter, K., Montgomery, P.L., Naehrig, M.: An analysis of affine coordinates for pairing computation. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol.?6487, pp. 1-0. Springer, Heidelberg (2010) CrossRef
  23. Le, D.P.: Fast Quadrupling of a Point in Elliptic Curve Cryptography. Cryptology ePrint Archive, Report 2011/039 (2011), ategory-non-proportional">http://eprint.iacr.org/
  24. Le, D.P., Liu, C.L.: Refinements of Miller’s Algorithm over Weierstrass Curves Revisited. The Computer Journal?54(10), 1582-591 (2011) CrossRef
  25. Lin, X., Zhao, C.A., Zhang, F., Wang, Y.: Computing the Ate pairing on elliptic curves with embedding degree k = 9. IEICE Trans. Fundam. Electron. Commun. Comput. Sci.?E91-A(9), 2387-393 (2008) CrossRef
  26. Miller, V.S.: The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology?17(4), 235-61 (2004) CrossRef
  27. Miyaji, A., Nakabayashi, M., Takano, S.: New Explicit Conditions of Elliptic Curve Traces for FR-Reduction. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences?84(5), 1234-243 (2001)
  28. Naehrig, M., Niederhagen, R., Schwabe, P.: New software speed records for cryptographic pairings. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol.?6212, pp. 109-23. Springer, Heidelberg (2010) CrossRef
  29. Pereira, G.C.C.F., Simplício, J.M.A., Naehrig, M., Barreto, P.S.L.M.: A family of implementation-friendly bn elliptic curves. J. Syst. Softw.?84, 1319-326 (2011) CrossRef
  30. Scott, M.: On the efficient implementation of pairing-based protocols. In: Chen, L. (ed.) IMACC 2011. LNCS, vol.?7089, pp. 296-08. Springer, Heidelberg (2011) CrossRef
  31. Scott, M., Barreto, P.S.L.M.: Compressed pairings. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.?3152, pp. 140-56. Springer, Heidelberg (2004) CrossRef
  32. Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L.J., Kachisa, E.J.: On the final exponentiation for calculating pairings on ordinary elliptic curves. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol.?5671, pp. 78-8. Springer, Heidelberg (2009) CrossRef
  33. Joseph, H.: Silverman: The Arithmetic of Elliptic Curves, 2nd edn. Springer (May 2009)
  34. Vercauteren, F.: Optimal pairings. IEEE Transactions on Information Theory?56(1), 455-61 (2010) CrossRef
  
• 作者单位：Duc-Phong Le (19)
  Chik How Tan (19)
  
  19. Temasek Laboratories, National University of Singapore, 5A Engineering Drive 1, #09-02, Singapore, 117411
  
• ISSN：1611-3349

文摘

At Pairing 2010, Lauter et al’s analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates. We first analyze Ate pairing computation using 4-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in the full extension field and one field inversion for several multiplications in a smaller field. Then, we focus on pairing computations over elliptic curves admitting a twist of degree 3. We propose new fast explicit formulas for Miller function that are comparable to formulas over even twisted curves. We further analyze pairing computation on cubic twisted curves by proposing efficient subfamilies of pairing-friendly elliptic curves with embedding degrees k--, and 15. These subfamilies allow us not only to obtain a very simple form of curve, but also lead to an efficient arithmetic and final exponentiation.