Abstract
Miller’s algorithm is at the heart of all pairing-based cryptosystems since it is used in the computation of pairing such as that of Weil or Tate and their variants. Most of the optimizations of this algorithm involve elliptic curves of particular forms, or curves with even embedding degree, or having an equation of a special form. Other improvements involve a reduction of the number of iterations.
In this article, we propose a variant of Miller’s formula which gives rise to a generically faster algorithm for any pairing friendly curve. Concretely, it provides an improvement in cases little studied until now, in particular when denominator elimination is not available. It allows for instance the use of elliptic curve with embedding degree not of the form 2i3j, and is suitable for the computation of optimal pairings. We also present a version with denominator elimination for even embedding degree. In our implementations, our variant saves between 10% and 40% in running time in comparison with the usual version of Miller’s algorithm without any optimization.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arène, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster computation of the Tate pairing. Preprint, Cryptology ePrint Archive: Report 2009/155 (2009), http://eprint.iacr.org/2009/155
Balasubramanian, R., Koblitz, N.: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes–Okamoto–Vanstone algorithm. J. Cryptology 11(2), 141–145 (1998)
Barreto, P.S.L.M., Galbraith, S.D., O’Eigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Des. Codes Cryptography 42(3), 239–271 (2007)
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–25. Springer, Heidelberg (2003)
Barreto, P.S.L.M., Lynn, B., Scott, M.: Efficient implementation of pairing-based cryptosystems. J. Cryptology 17(4), 321–334 (2004)
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–331. Springer, Heidelberg (2006)
Bernstein, D., Lange, T.: Explicit-formulas database (2010), http://www.hyperelliptic.org/EFD/
Blake, I.F., Kumar Murty, V., Xu, G.: Refinements of Miller’s algorithm for computing the Weil/Tate pairing. J. Algorithms 58(2), 134–149 (2006)
Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curves Cryptography. London Mathematical Society Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005)
Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003); Extended abstract in proc. of Crypto 2001
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete mathematics and its applications. Chapman & Hall, Boca Raton (2006)
Costello, C., Hisil, H., Boyd, C., Nieto, J.M.G., Wong, K.K.-H.: Faster pairings on special Weierstrass curves. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 89–101. Springer, Heidelberg (2009)
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–242. Springer, Heidelberg (2010)
El Mrabet, N., Nègre, C.: Finite field multiplication combining AMNS and DFT approach for pairing cryptography. In: Boyd, C., González Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 422–436. Springer, Heidelberg (2009)
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptology 23(2), 224–280 (2010)
Heß, F.: Pairing lattices. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 18–38. Springer, Heidelberg (2008)
Heß, F., Smart, N.P., Vercauteren, F.: The Eta pairing revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)
Ionica, S., Joux, A.: Another approach to pairing computation in Edwards coordinates. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 400–413. Springer, Heidelberg (2008)
Ionica, S., Joux, A.: Pairing the volcano. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS-IX. LNCS, vol. 6197, pp. 201–218. Springer, Heidelberg (2010)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptology 17(4), 263–276 (2000); Extended abstract in proc. of ANTS 2000
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–36. Springer, Heidelberg (2005)
Lin, X., Zhao, C., Zhang, F., Wang, Y.: Computing the Ate pairing on elliptic curves with embedding degree k = 9. IEICE Transactions 91-A(9), 2387–2393 (2008)
Matsuda, S., Kanayama, N., Heß, F., Okamoto, E.: Optimised versions of the Ate and twisted Ate pairings. IEICE Transactions 92-A(7), 1660–1667 (2009)
Miller, V.S.: The Weil pairing, and its efficient calculation. J. Cryptology 17(4), 235–261 (2004)
Shoup, V.: NTL: a library for doing number theory (2009), http://www.shoup.net/ntl/
Vercauteren, F.: Optimal pairings. IEEE Transactions of Information Theory 56, 455–461 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boxall, J., El Mrabet, N., Laguillaumie, F., Le, DP. (2010). A Variant of Miller’s Formula and Algorithm. In: Joye, M., Miyaji, A., Otsuka, A. (eds) Pairing-Based Cryptography - Pairing 2010. Pairing 2010. Lecture Notes in Computer Science, vol 6487. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17455-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-17455-1_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17454-4
Online ISBN: 978-3-642-17455-1
eBook Packages: Computer ScienceComputer Science (R0)