Implementing Cryptographic Pairings at Standard Security Levels

详细信息    查看全文

• 关键词：elliptic curve cryptology ; pairings ; implementation
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8804
• 期：1
• 页码：28-46
• 全文大小：320 KB
• 参考文献：1. Aranha, D.F., Fuentes-Casta?eda, L., Knapp, E., Menezes, A., Rodríguez-Henríquez, F.: Implementing pairings at the 192-bit security level. In: Abdalla, M., Lange, T. (eds.) Pairing 2012. LNCS, vol.?7708, pp. 177-95. Springer, Heidelberg (2013) CrossRef
  2. 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
  3. Avanzi, R.M., Mih?ilescu, P.: Generic efficient arithmetic algorithms for PAFFs (processor adequate finite fields) and related algebraic structures (extended abstract). In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol.?3006, pp. 320-34. Springer, Heidelberg (2004) CrossRef
  4. Bailey, D.V., Paar, C.: Efficient arithmetic in finite field extensions with applications in elliptic curve cryptography. Journal of Cryptology?14(3), 153-76 (2001)
  5. Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol.?8441, pp. 1-6. Springer, Heidelberg (2014) CrossRef
  6. Blazy, O., Fuchsbauer, G., Izabachène, M., Jambert, A., Sibert, H., Vergnaud, D.: Batch Groth-Sahai. In: Zhou, J., Yung, M. (eds.) ACNS 2010. LNCS, vol.?6123, pp. 218-35. Springer, Heidelberg (2010) CrossRef
  7. 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
  8. Chatterjee, S., Menezes, A.: On cryptographic protocols employing asymmetric pairings -the role of / ψ revisited. Discrete Applied Mathematics?159, 1311-322 (2011) CrossRef
  9. Freemann, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Journal of Cryptology?23(2), 224-80 (2010) CrossRef
  10. Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Applied Mathematics?156(16), 3113-121 (2008) CrossRef
  11. Granger, R., Page, D., Smart, N.P.: High security pairing-based cryptography revisited. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol.?4076, pp. 480-94. Springer, Heidelberg (2006) CrossRef
  12. Granlund, T., et al.: gmp -GNU multiprecision library. Version 5.0.3, ategory-non-proportional">http://gmplib.org/
  13. Hess, F.: Pairing lattices. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol.?5209, pp. 18-8. Springer, Heidelberg (2008) CrossRef
  14. Hess, F., Smart, N.P., Vercauteren, F.: The eta pairing revisited. IEEE Transactions on Information Theory?52(10), 4595-602 (2006) CrossRef
  15. Karim Belabas and the PARI?Group, Bordeaux. PARI/GP. Version 2.5.0, ategory-non-proportional">http://pari.math.u-bordeaux.fr/
  16. 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
  17. Miller, V.S.: The Weil pairing, and its efficient calculation. Journal of Cryptology?17, 235-61 (2004) CrossRef
  18. Nogami, Y., Kato, H., Nekado, K., Morikawa, Y.: Efficient exponentiation in extensions of finite fields without fast Frobenius mappings. ETRI Journal?30(6), 818-25 (2008) CrossRef
  19. Panario, D., Thomson, D.: Efficient / pth root computations in finite fields of characteristic / p. Designs, Codes and Cryptography?50(3), 351-58 (2009) CrossRef
  20. Pereira, G.C.C.F., Simplcio Jr., M.A., Naehrig, M., Barreto, P.S.L.M.: A family of implementation-friendly BN elliptic curves. Journal of Systems and Software?84(8), 1319-326 (2011) CrossRef
  21. 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
  22. Smart, N., et al.: ECRYPT II yearly report on algorithms and keysizes (2009-2010). Technical Report D.SPA.13, European Network of Excellence in Cryptology II (March 2010), ategory-non-proportional">http://www.ecrypt.eu.org/documents/D.SPA.13.pdf
  23. Vercauteren, F.: Optimal pairings. IEEE Transactions on Information Theory?56(1), 455-61 (2010) CrossRef
  24. Yao, A.C.-C.: On the evaluation of powers. SIAM Journal on Computing?5(1), 100-03 (1976) CrossRef
  
• 作者单位：Andreas Enge (18)
  Jér?me Milan (19)
  
  18. INRIA, LFANT, CNRS, UMR 5251, Univ. Bordeaux, IMB, 33400, Talence, France
  19. INRIA, CNRS, UMR 7161, école polytechnique, LIX, 91128, Palaiseau, France
  
• ISSN：1611-3349

文摘

This study reports on an implementation of cryptographic pairings in a general purpose computer algebra system. For security levels equivalent to the different AES flavours, we exhibit suitable curves in parametric families and show that optimal ate and twisted ate pairings exist and can be efficiently evaluated. We provide a correct description of Miller’s algorithm for signed binary expansions such as the NAF and extend a recent variant due to Boxall et al. to addition-subtraction chains. We analyse and compare several algorithms proposed in the literature for the final exponentiation. Finally, we give recommendations on which curve and pairing to choose at each security level.