Abstract
Edwards gave a new form of elliptic curves in [1], and these curves were introduced to cryptography by Bernstein and Lange in [2]. The Edwards curves enjoy faster addition and doubling operations, so they are very attractive for elliptic curve cryptography.
In 2006, Blake, Murty and Xu proposed three refinements to Millers algorithm for computing Weil/Tate pairings over Weierstraß curves. In this paper we extend their method to Edwards curve and propose a faster algorithm for computing pairings with Edwards coordinates, which comes from the analysis of divisors of rational functions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Edwards, H.M.: A Normal Form for Elliptic Curves. Bulletin of the American Mathematical Society 44, 393–442 (2007)
Bernstein, D.J., Lange, T.: Faster Addition and Doubleling on Elliptic Curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)
Menezes, A.J., Okamoto, T., Vanstone, S.A.: Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions on Information Theory (1993)
Frey, G., Rück, H.G.: A Remark Concerning m-divisibility and the Discrete Logarithm in the Divisor Class Group of Curves. Mathematics of Computation 62, 865–874 (1994)
Boneh, D., Franklin, M.: Identity-based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Joux, A.: A One Round Protocol for Tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–393. Springer, Heidelberg (2000)
Boneh, D., Lynn, B., Shacham, H.: Short Signature from the Weil Pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Miller, V.S.: The Weil Pairing, and its Efficient Calculation. Journal of Cryptology 17(4), 235–261 (2004)
Blake, I.F., Sroussi, G., Smart, P.N.: Advances in Elliptic Curve Cryptography. Cambridge University Press, Cambridge (2005)
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards Curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)
Das, M.P.L., Sarkar, P.: Pairing Computation on Twisted Edwards form Elliptic Curves. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 192–210. Springer, Heidelberg (2008)
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)
Aréne, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster Pairing Computation. Cryptology ePrint Archive, Report 2009/155 (2009)
Barreto, P.S., Lynn, B., Scott, M.: Efficient Implementation of Pairing-based Cryptosystems. Journal of Cryptology 17, 321–334 (2004)
Hartshorne, R.: Algebraic Geometry. Graduate Texts in Mathematics. Springer, Heidelberg (1977)
Blake, I.F., Murty, V.K., Xu, G.: Refinements of Miller’s Algorithm for Computing the Weil/Tate pairing. Journal of Algorithms 58, 134–149 (2006)
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
Xu, L., Lin, D. (2010). Refinement of Miller’s Algorithm Over Edwards Curves. In: Pieprzyk, J. (eds) Topics in Cryptology - CT-RSA 2010. CT-RSA 2010. Lecture Notes in Computer Science, vol 5985. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11925-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-11925-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11924-8
Online ISBN: 978-3-642-11925-5
eBook Packages: Computer ScienceComputer Science (R0)