Huseyin Hisil
Skip Abstract Section
Abstract
A paper by Karati and Sarkar at Asiacrypt’17 has pointed out the potential for Kummer lines in genus 1, by observing that their SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this article, we extend this work and significantly simplify the treatment of Karati and Sarkar. We show that their Kummer line is the x-line of a Montgomery curve translated by a point of order two, and exhibit a natural isomorphism to the y-line of a twisted Edwards curve. Moreover, we show that the Kummer line presented by Gaudry and Lubicz can be obtained via the action of a point of order two on the y-line of an Edwards curve. The maps connecting these curves and lines are all very simple. As a result, a cryptographic implementation can use the arithmetic that is optimal for its instruction set at negligible cost.
- D. J. Bernstein. 2006a. Curve25519: New Diffie–Hellman speed records. In Proceedings of the 9th International Conference on Theory and Practice of Public-Key Cryptography. 207--228. DOI:https://doi.org/10.1007/11745853_14Google Scholar
Digital Library
- D. J. Bernstein. 2006b. Elliptic vs. Hyperelliptic, part I. Talk at ECC (Slides retrieved from http://cr.yp.to/talks/2006.09.20/slides.pdf).Google Scholar
- D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters. 2008. Twisted Edwards curves. In Proceedings of the 1st International Conference on Cryptology in Africa (Lecture Notes in Computer Science), S. Vaudenay (Ed.), Vol. 5023. Springer, 389--405. DOI:https://doi.org/10.1007/978-3-540-68164-9_26Google Scholar
- D. J. Bernstein, C. Chuengsatiansup, T. Lange, and P. Schwabe. 2014. Kummer strikes back: New DH speed records. In Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, Palash Sarkar and Tetsu Iwata (Eds.). Springer Berlin, 317--337. DOI:https://doi.org/10.1007/978-3-662-45611-8_17Google Scholar
- D. J. Bernstein and T. Lange. 2007. Faster addition and doubling on elliptic curves. In Proceedings of the 13th International Conference on the Theory and Application of Cryptology and Information Security. 29--50. DOI:https://doi.org/10.1007/978-3-540-76900-2_3Google Scholar
- D. J. Bernstein and T. Lange. 2015. Explicit-Formulas Database. Retrieved from: http://hyperelliptic.org/EFD/g1p/auto-edwards-yzsquared.html.Google Scholar
- W. Bosma, J. Cannon, and C. Playoust. 1997. The Magma algebra system. I. The user language. J. Symbol. Comput. 24, 3--4 (1997), 235--265. DOI:https://doi.org/10.1006/jsco.1996.0125Google ScholarDigital Library
- W. Castryck, S. D. Galbraith, and R. R. Farashahi. 2008. Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation. Cryptology ePrint Archive, Report 2008/218. Retrieved from: http://eprint.iacr.org/2008/218.Google Scholar
- T. Chou. 2015. Sandy2x. Message on the curves mailing list at Retrieved from: https://moderncrypto.org/mail-archive/curves/2015/000637.html.Google Scholar
- D. V. Chudnovsky and G. V. Chudnovsky. 1986. Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7, 4 (1986), 385--434.Google ScholarDigital Library
- J. S. Coron. 1999. Resistance against differential power analysis for elliptic curve cryptosystems. In Proceedings of the Cryptographic Hardware and Embedded Systems Conference (CHES’99), Çetin K. Koç and C. Paar (Eds.), Vol. 1717. 292--302.Google ScholarCross Ref
- C. Costello and P. Longa. 2015. FourQ: Four-dimensional decompositions on a Q-curve over the Mersenne prime. In Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security. 214--235. DOI:https://doi.org/10.1007/978-3-662-48797-6_10Google Scholar
- W. Diffie and M. E. Hellman. 1976. New directions in cryptography. IEEE Trans. Inform. Theor. 22, 6 (1976), 644--654. DOI:https://doi.org/10.1109/TIT.1976.1055638Google ScholarDigital Library
- M. Düll, B. Haase, G. Hinterwälder, M. Hutter, C. Paar, A. H. Sánchez, and P. Schwabe. 2015. High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers. Design, Codes and Cryptog. 77, 2 (2015). Retrieved from: http://cryptojedi.org/papers/#mu25519.Google Scholar
- H. M. Edwards. 2007. A normal form for elliptic curves. Bull. Amer. Math. Soc. 44, 3 (July 2007), 393--422.Google ScholarCross Ref
- R. R. Farashahi and S. G. Hosseini. 2017. Differential addition on twisted Edwards curves. In Proceedings of the 22nd Australasian Conference on Information Security and Privacy (ACISP’17). 366--378. DOI:https://doi.org/10.1007/978-3-319-59870-3_21Google Scholar
- R. R. Farashahi, D. Moody, and H. Wu. 2012. Isomorphism classes of Edwards curves over finite fields. Finite Fields Their Appl. 18, 3 (2012), 597--612. DOI:https://doi.org/10.1016/j.ffa.2011.12.004Google ScholarCross Ref
- R. R. Farashahi and I. E. Shparlinski. 2010. On the number of distinct elliptic curves in some families. Des. Codes Cryptog. 54, 1 (2010), 83--99. DOI:https://doi.org/10.1007/s10623-009-9310-2Google ScholarDigital Library
- A. Faz-Hernández and J. López. 2015. Fast implementation of Curve25519 using AVX2. In Proceedings of the 4th International Conference on Cryptology and Information Security in Latin America. 329--345. DOI:https://doi.org/10.1007/978-3-319-22174-8_18Google Scholar
- S. D. Galbraith. 2012. Mathematics of Public Key Cryptography. Cambridge University Press. Retrieved from: https://www.math.auckland.ac.nz/ sgal018/crypto-book/crypto-book.html.Google Scholar
- P. Gaudry. 2006. Variants of the Montgomery form based on theta functions. Retrieved from: http://www.fields.utoronto.ca/audio/06-07/number_theory/gaudry/.Google Scholar
- P. Gaudry. 2007. Fast genus 2 arithmetic based on Theta functions. J. Math. Cryptol. 1, 3 (2007), 243--265.Google ScholarCross Ref
- P. Gaudry and D. Lubicz. 2009. The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines. Finite Fields Their Appl. 15, 2 (2009), 246--260. DOI:https://doi.org/10.1016/j.ffa.2008.12.006Google ScholarDigital Library
- H. Hisil. 2010. Elliptic Curves, Group Law, and Efficient Computation. Ph.D. Dissertation. Queensland University of Technology.Google Scholar
- H. Hisil, K. K. Wong, G. Carter, and E. Dawson. 2008. Twisted Edwards curves revisited. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Josef Pieprzyk (Ed.). Springer Berlin, 326--343.Google Scholar
- S. Karati and P. Sarkar. 2017a. Connecting Legendre with Kummer and Edwards. Cryptology ePrint Archive, Report 2017/1205. Retrieved from: https://eprint.iacr.org/2017/1205.Google Scholar
- S. Karati and P. Sarkar. 2017b. Kummer for genus one over prime order fields. In Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security. 3--32. DOI:https://doi.org/10.1007/978-3-319-70697-9_1Google Scholar
- N. Koblitz. 1987. Elliptic curve cryptosystems. Math. Comp. 48 (1987), 203--209.Google ScholarDigital Library
- V. Miller. 1986. Use of elliptic curves in cryptography. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security. Lecture Notes in Computer Science, Vol. 218. Springer Berlin, 417--426.Google ScholarCross Ref
- P. L. Montgomery. 1987. Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48, 177 (1987), 243--264.Google ScholarCross Ref
- J. Renes. 2018. Computing isogenies between Montgomery curves using the action of (0, 0). In Proceedings of the International Conference on Post-Quantum Cryptography. Lecture Notes in Computer Science, Vol. 10786. Springer, 229--247. Retrieved from: https://ia.cr/2017/1198.Google Scholar
- J. Renes and B. Smith. 2017. qDSA: Small and secure digital signatures with curve-based Diffie--Hellman key pairs. In Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer International Publishing, 273--302. DOI:https://doi.org/10.1007/978-3-319-70697-9_10Google Scholar
- J. H. Silverman. 2009. The Arithmetic of Elliptic Curves, 2nd Edition. Springer. Retrieved from: http://link.springer.com/book/10.1007%2F978-0-387-09494-6.Google Scholar
- A. Takahashi, M. Tibouchi, and M. Abe. 2018. New Bleichenbacher Records: Practical Fault Attacks on qDSA Signatures. Cryptology ePrint Archive, Report 2018/396. Retrieved from: https://eprint.iacr.org/2018/396.Google Scholar
- The Sage Developers. 2018. SageMath, the Sage Mathematics Software System (version 8.1). Retrieved from: https://sagemath.org.Google Scholar
Index Terms
- On Kummer Lines with Full Rational 2-torsion and Their Usage in Cryptography
Recommendations
Twisted Edwards curves
AFRICACRYPT'08: Proceedings of the Cryptology in Africa 1st international conference on Progress in cryptologyThis paper introduces "twisted Edwards curves," a generalization of the recently introduced Edwards curves; shows that twisted Edwards curves include more curves over finite fields, and in particular every elliptic curve in Montgomery form; shows how to ...
How to Construct CSIDH on Edwards Curves
Topics in Cryptology – CT-RSA 2020AbstractCSIDH is an isogeny-based key exchange protocol proposed by Castryck, Lange, Martindale, Panny, and Renes in 2018. CSIDH is based on the ideal class group action on -isomorphism classes of Montgomery curves. In order to calculate the class group ...
Comments