Abstract
We provide a simple and exact formula for the minimum Miller loop length in Ate i pairing based on Brezing–Weng curves, in terms of the involved parameters, under a mild condition on the parameters. It will also be shown that almost all cryptographically useful/meaningful parameters satisfy the mild condition. Hence the simple and exact formula is valid for them. It will also turn out that the formula depends only on essentially two parameters, providing freedom to choose the other parameters to address the design issues other than minimizing the loop length.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Atkin A., Morain F.: Elliptic curves and primality proving. Math. Comput. 61, 29–68 (1993)
Barreto P.S.L.M., Galbraith S., Ó hÉigeartaigh C., Scott M.: Efficient pairing computation on supersingular abelian varieties. Des. Codes Cryptogr. 42(3), 239–271 (2007)
Boneh D., Franklin M.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
Boneh D., Lynn B., Shacham H.: Short signatures from the Weil pairing. J. Cryptol. 17(4), 297–319 (2004)
Barreto P.S.L.M., Naehrig M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds) SAC 2005., pp. 319–331. LNCS, vol 3897. Springer (2006)
Brezing F., Weng A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptogr. 37(1), 133–141 (2005)
Bzdȩga B.: On the height of cyclotomic polynomials. arXiv preprint, arXiv:1012.3897v1, Dec (2010).
Cauchy A.L.: Exercises de mathematique. Oeuvres 9(2), 122 (1829)
Duursma I., Lee H.: Tate pairing implementation for hyperelliptic curves y 2 = x p −x + d. In: Advances in Cryptography: Proceedings of AsiaCrypt 2003, Lecture Notes in Computer Science, vol. 2894, pp. 111–123. Springer, New York (2003).
Freeman D.: Constructing pairing-friendly elliptic curves with embedding degree 10. In: Hess, F., Pauli, S., Pohst, M. (eds) ANTS 2006 LNCS, vol 4076., pp. 452–465. Springer, Heidelberg (2006)
Freeman D., Scott M., Teske E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23, 224–280 (2010)
Galbraith S., McKee J., Valenca P.: Ordinary abelian varieties having small embedding degree. Finite Fields Appl. 13, 800–814 (2007)
Hitt L.: On the minimal embedding field. In: Proceedings of Pairing 2007, LNCS 4575, vol. 294–301 (2007).
Hong H., Lee E., Lee H.S., Park C.M: Maximum gap in inverse cyclotomic polynomials. arXiv Preprint, arXiv 1101.4255, Jan (2011).
Hess F., Smart N.P., Vercauteren F.: The eta pairing revisited. IEEE Trans. Inform. Theory 52, 4595–4602 (2006)
Joux A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptol. 17(4), 263–276 (2004)
Lee E., Lee H.S, Park C.M: Efficient and generalized pairing computation on Abelian varieties. IEEE Trans. Inform. Theory 55(4), 1793–1803 (2009)
Mille V.: The Weil pairing and its efficient calculation. J. Cryptol. 17, 235–261 (2004)
Moree P.: Inverse cyclotomic polynomials. J. Numb. Theory 129(3), 667–680 (2009)
Sakai R., Ohgishi K., Kasahara M.: Cryptosystems based on pairing. In: Proceedings of Symposium on Cryptography and Information Security, SCIS 2000 (2000).
Sutherland A.V.: Computing Hilbert class polynomials with the Chinese remainder theorem. Math. Comp. 80, 501–538 (2011)
Vercauteren F.: Optimal pairings. IEEE Trans. Inform. Theory 56(1), 455–461 (2010)
Zhao C., Zhang F., Huang J.: A note on the ate pairing. Int. J. Inform. Secur. 7(6), 379–382 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by A. Enge.
Rights and permissions
About this article
Cite this article
Hong, H., Lee, E., Lee, HS. et al. Simple and exact formula for minimum loop length in Ate i pairing based on Brezing–Weng curves. Des. Codes Cryptogr. 67, 271–292 (2013). https://doi.org/10.1007/s10623-011-9605-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-011-9605-y