Fast 4 way vectorized ladder for the complete set of Montgomery curves
Loading...
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
Abstract
This paper introduces 4 way vectorization of Montgomery ladder on any Montgomery form elliptic curve. Our algorithm\rtakes 2M4 + 1S\r4\r(M4\r: A vector of four field multiplications S\r4\r: A vector of four field squarings) per ladder step for variable-scalar\rvariable-point multiplication. This is a theoretical improvement over the squared Kummer ladder which takes 2M4 + 1S\r4 + 1d\r4\rper\rladder step. This paper also introduces new formulas for doing arithmetic over GF(2255 − 19). We provide two implementations\rof curve25519 using our proposed algorithm. The first implementation uses AVX2 instruction set and takes 98484 cycles. This\ris competitive with the current speed record of 95437 cycles by Nath and Sarkar. The second implementation uses AVX-512\rinstruction set and takes 74368 cycles. This sets the new speed record over Faz-Hernandez L ´ opez and Dahab’s implementation ´\rwhich takes 81600 cycles.
Description
Keywords
Bilgisayar Bilimleri- Yazılım Mühendisliği, Bilgisayar Bilimleri, Yazılım Mühendisliği
Fields of Science
Citation
V. Miller “Use of elliptic curves in cryptography” in CRYPTO’85 ser. LNCS vol. 218. Springer 1985 pp. 417–426.N. Koblitz “Elliptic curve cryptosystems” Mathematics of Computation vol. 48 no. 177 pp. 203–209 January 1987.P. Montgomery “Speeding the Pollard and elliptic curve methods of factorization” Mathematics of computation vol. 48 no. 177 pp.243–264 1987.D. Bernstein “Curve25519: New Diffie-Hellman speed records” in Public Key Cryptography - PKC 2006 9th International Conference on Theory and Practice of Public-Key Cryptography New York NY USA April 24-26 2006 Proceedings ser. Lecture Notes in Computer Science M. Yung Y. Dodis A. Kiayias and T. Malkin Eds. vol. 3958. Springer 2006 pp. 207–228. [Online]. Available: https://doi.org/10.1007/11745853 14E. Brier and M. Joye “Weierstraß elliptic curves and side-channel attacks” in Public Key Cryptography 5th International Workshop on Practice and Theory in Public Key Cryptosystems PKC 2002 Paris France February 12-14 2002 Proceedings ser. Lecture Notes in Computer Science D. Naccache and P. Paillier Eds. vol. 2274. Springer 2002 pp. 335–345. [Online]. Available: https://doi.org/10.1007/3-540-45664-3 24J. López and R. Dahab “Fast multiplication on elliptic curves over GF(2m ) without precomputation” in Cryptographic Hardware and Embedded Systems First International Workshop CHES’99 Worcester MA USA August 12-13 1999 Proceedings ser. Lecture Notes in Computer Science Ç. Koç and C. Paar Eds. vol. 1717. Springer 1999 pp. 316–327. [Online]. Available: https://doi.org/10.1007/3-540-48059-5 27W. Castryck S. Galbraith and R. R. Farashahi “Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation” Cryptology ePrint Archive Report 2008/218 2008 https://eprint.iacr.org/2008/218.D. J. Bernstein T. Lange and R. Rezaeian Farashahi “Binary Edwards curves” in Cryptographic Hardware and Embedded Systems – CHES 2008 E. Oswald and P. Rohatgi Eds. Berlin Heidelberg: Springer Berlin Heidelberg 2008 pp. 244–265.R. Rezaeian Farashahi and S. G. Hosseini “Differential addition on binary elliptic curves” in Arithmetic of Finite Fields S. Duquesne and S. Petkova-Nikova Eds. Cham: Springer International Publishing 2016 pp. 21–35.R. Rezaeian Farashahi and S. G. Hosseini “Differential addition on twisted Edwards curves” in Information Security and Privacy - 22nd Australasian Conference ACISP 2017 Auckland New Zealand July 3-5 2017 Proceedings Part II ser. Lecture Notes in Computer Science J. Pieprzyk and S. Suriadi Eds. vol. 10343. Springer 2017 pp. 366–378. [Online]. Available: https://doi.org/10.1007/978-3-319-59870-3 21D. Chudnovsky and G. Chudnovsky “Sequences of numbers generated by addition in formal groups and new primality and factorization tests” Advances in Applied Mathematics vol. 7 no. 4 pp. 385–434 1986.P. Gaudry “Fast genus 2 arithmetic based on Theta functions” Journal of Mathematical Cryptology (JMC) vol. 1 no. 3 pp. 243–265 2007.P. Gaudry and D. Lubicz “The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines” Finite Fields and Their Applications vol. 15 no. 2 pp. 246 – 260 2009. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1071579708000804J. Renes and B. Smith “qDSA: small and secure digital signatures with curve-based Diffie-Hellman key pairs” in Advances in Cryptology - ASIACRYPT 2017 ser. Lecture Notes in Computer Science T. Takagi and T. Peyrin Eds. vol. 10625. Springer 2017 pp. 273–302. [Online]. Available: https://doi.org/10.1007/978-3-319-70697-9 10P. Gaudry and E. Schost “Genus 2 point counting over prime fields” J. Symb. Comput. vol. 47 no. 4 pp. 368–400 2012. [Online]. Available: http://dx.doi.org/10.1016/j.jsc.2011.09.003D. Bernstein C. Chuengsatiansup T. Lange and P. Schwabe “Kummer strikes back: New DH speed records” in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security Kaoshiung Taiwan R.O.C. December 7-11 2014. Proceedings Part I ser. Lecture Notes in Computer Science P. Sarkar and T. Iwata Eds. vol. 8873. Springer 2014 pp. 317–337. [Online]. Available: https://doi.org/10.1007/978-3-662-45611-8 17T. Chou “Sandy2x: New Curve25519 speed records” in Selected Areas in Cryptography - SAC 2015 - 22nd International Conference Sackville NB Canada August 12-14 2015 Revised Selected Papers ser. Lecture Notes in Computer Science O. Dunkelman and L. Keliher Eds. vol. 9566. Springer 2015 pp. 145–160. [Online]. Available: https://doi.org/10.1007/978-3-319-31301-6S. Karati and P. Sarkar “Kummer for genus one over prime order fields” in Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security Hong Kong China December 3-7 2017 Proceedings Part II ser. Lecture Notes in Computer Science T. Takagi and T. Peyrin Eds. vol. 10625. Springer 2017 pp.3–32. [Online]. Available: https://doi.org/10.1007/978-3-319-70697-9 1D. Bernstein and T. Lange Montgomery Curves and the Montgomery Ladder. Cambridge University Press 2017 pp. 82–115.C. Costello and B. Smith “Montgomery curves and their arithmetic - The case of large characteristic fields” J. Cryptographic Engineering vol. 8 no. 3 pp. 227–240 2018. [Online]. Available: https://doi.org/10.1007/s13389-017-0157-6D. Bernstein and P. Schwabe “NEON crypto” in Cryptographic Hardware and Embedded Systems – CHES 2012 ser. Lecture Notes in Computer Science E. Prouff and P. Schaumont Eds. vol. 7428. Berlin Heidelberg: Springer Berlin Heidelberg 2012 pp. 320–339.K. Nath and P. Sarkar “Efficient arithmetic in (pseudo-)mersenne prime order fields” Cryptology ePrint Archive Report 2018/985 2018 https://eprint.iacr.org/2018/985.T. Oliveira J. López H. Hışıl A. Faz-Hernández and F. Rodrı́guez-Henrı́quez “How to (pre–)compute a ladder – improving the performance of X25519 and X448” in Selected Areas in Cryptography - SAC 2017 - 24th International Conference Ottawa ON Canada August 16-18 2017 Revised Selected Papers ser. Lecture Notes in Computer Science C. Adams and J. Camenisch Eds. vol. 10719. Springer 2017 pp. 172–191. [Online]. Available: https://doi.org/10.1007/978-3-319-72565-9 9A. Faz-Hernández J. López and R. Dahab “High-performance implementation of elliptic curve cryptography using vector instructions” ACM Trans. Math. Softw. vol. 45 no. 3 Jul. 2019. [Online]. Available: https://doi.org/10.1145/3309759K. Nath and P. Sarkar “Efficient 4-way vectorizations of the Montgomery ladder” Cryptology ePrint Archive Report 2020/378 2020 https://eprint.iacr.org/2020/378.T. Takagi and T. Peyrin Eds. Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security Hong Kong China December 3-7 2017 Proceedings Part II ser. Lecture otes in Computer Science vol. 10625. Springer 2017. [Online]. Available: https://doi.org/10.1007/978-3-319-70697-9
WoS Q
Scopus Q
Source
International Journal of Information Security Science
Volume
11
Issue
2
Start Page
12
End Page
24
Collections
