{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T10:45:35Z","timestamp":1782125135962,"version":"3.54.5"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T00:00:00Z","timestamp":1564444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Intel and Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo (FAPESP) as part of the project \u201cSecure Execution of Cryptographic Algorithms\u201d","award":["14\/50704-7"],"award-info":[{"award-number":["14\/50704-7"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>Elliptic curve cryptosystems are considered an efficient alternative to conventional systems such as DSA and RSA. Recently, Montgomery and Edwards elliptic curves have been used to implement cryptosystems. In particular, the elliptic curves Curve25519 and Curve448 were used for instantiating Diffie-Hellman protocols named X25519 and X448. Mapping these curves to twisted Edwards curves allowed deriving two new signature instances, called Ed25519 and Ed448, of the Edwards Digital Signature Algorithm. In this work, we focus on the secure and efficient software implementation of these algorithms using SIMD parallel processing. We present software techniques that target the Intel AVX2 vector instruction set for accelerating prime field arithmetic and elliptic curve operations. Our contributions result in a high-performance software library for AVX2-ready processors. For example, our library computes digital signatures 19% (for Ed25519) and 29% (for Ed448) faster than previous optimized implementations. Also, our library improves by 10% and 20% the execution time of X25519 and X448, respectively.<\/jats:p>","DOI":"10.1145\/3309759","type":"journal-article","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T19:52:26Z","timestamp":1564516346000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["High-performance Implementation of Elliptic Curve Cryptography Using Vector Instructions"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5502-8666","authenticated-orcid":false,"given":"Armando","family":"Faz-Hern\u00e1ndez","sequence":"first","affiliation":[{"name":"Institute of Computing, University of Campinas, S\u00e3o Paulo, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5139-0158","authenticated-orcid":false,"given":"Julio","family":"L\u00f3pez","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas, S\u00e3o Paulo, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7002-875X","authenticated-orcid":false,"given":"Ricardo","family":"Dahab","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas, S\u00e3o Paulo, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,30]]},"reference":[{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/648025.744368"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33481-8_10"},{"key":"e_1_2_1_5_1","volume-title":"Cryptography Coding Standard. Retrieved","author":"Aumasson Jean-Philippe","year":"2018","unstructured":"Jean-Philippe Aumasson , Tanja Lange , Nick Mathewson , Samuel Neves , and Diego F. Aranha . 2013 . Cryptography Coding Standard. Retrieved Dec 10, 2018 from https:\/\/cryptocoding.net\/. Jean-Philippe Aumasson, Tanja Lange, Nick Mathewson, Samuel Neves, and Diego F. Aranha. 2013. Cryptography Coding Standard. Retrieved Dec 10, 2018 from https:\/\/cryptocoding.net\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11745853_14"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68164-9_26"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45611-8_17"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-012-0027-1"},{"key":"e_1_2_1_10_1","first-page":"5","article-title":"EdDSA for more curves","volume":"2015","author":"Bernstein Daniel J.","year":"2015","unstructured":"Daniel J. Bernstein , Simon Josefsson , Tanja Lange , Peter Schwabe , and Bo-Yin Yang . 2015 . EdDSA for more curves . Cryptol. ePrint Arch. 2015 , 677 (2015), 5 . Daniel J. Bernstein, Simon Josefsson, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. 2015. EdDSA for more curves. Cryptol. ePrint Arch. 2015, 677 (2015), 5.","journal-title":"Cryptol. ePrint Arch."},{"key":"e_1_2_1_11_1","volume-title":"Bernstein and Tanja Lange","author":"Daniel","year":"2015","unstructured":"Daniel J. Bernstein and Tanja Lange . 2015 . SafeCurves: Choosing safe curves for elliptic-curve cryptography. Retrieved March 2018 from http:\/\/safecurves.cr.yp.to. Daniel J. Bernstein and Tanja Lange. 2015. SafeCurves: Choosing safe curves for elliptic-curve cryptography. Retrieved March 2018 from http:\/\/safecurves.cr.yp.to."},{"key":"e_1_2_1_12_1","volume-title":"Bernstein and Tanja Lange","author":"Daniel","year":"2017","unstructured":"Daniel J. Bernstein and Tanja Lange . 2017 . eBACS: ECRYPT Benchmarking of Cryptographic Systems. Retrieved July 1, 2017 from http:\/\/bench.cr.yp.to\/. Daniel J. Bernstein and Tanja Lange. 2017. eBACS: ECRYPT Benchmarking of Cryptographic Systems. Retrieved July 1, 2017 from http:\/\/bench.cr.yp.to\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33027-8_19"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-31301-6_8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48797-6_10"},{"key":"e_1_2_1_16_1","first-page":"443","article-title":"Fast algorithms for large-integer arithmetic. In Prime Numbers: A Computational Perspective. Springer, New York, NY","volume":"9","author":"Crandall Richard","year":"2005","unstructured":"Richard Crandall and Carl Pomerance . 2005 . Fast algorithms for large-integer arithmetic. In Prime Numbers: A Computational Perspective. Springer, New York, NY , Chapter 9 , 443 -- 539 . Richard Crandall and Carl Pomerance. 2005. Fast algorithms for large-integer arithmetic. In Prime Numbers: A Computational Perspective. Springer, New York, NY, Chapter 9, 443--539.","journal-title":"Chapter"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646692.703439"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-014-0085-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22174-8_18"},{"key":"e_1_2_1_20_1","volume-title":"Instruction Tables: Lists of Instruction Latencies, Throughputs and Micro-operation Breakdowns for Intel, AMD and VIA CPUs","author":"Fog Agner","year":"2016","unstructured":"Agner Fog . 2016 . Instruction Tables: Lists of Instruction Latencies, Throughputs and Micro-operation Breakdowns for Intel, AMD and VIA CPUs . Technical University of Denmark . Retrieved from http:\/\/www.agner.org\/optimize\/instruction_tables.pdf. Agner Fog. 2016. Instruction Tables: Lists of Instruction Latencies, Throughputs and Micro-operation Breakdowns for Intel, AMD and VIA CPUs. Technical University of Denmark. Retrieved from http:\/\/www.agner.org\/optimize\/instruction_tables.pdf."},{"key":"e_1_2_1_21_1","series-title":"Lecture Notes in Computer Science","volume-title":"Vanstone","author":"Gallant Robert P.","year":"2001","unstructured":"Robert P. Gallant , Robert J. Lambert , and Scott A . Vanstone . 2001 . Faster point multiplication on elliptic curves with efficient endomorphisms. In Proceedings of the Conference on Advances in Cryptology (CRYPTO\u201901), Lecture Notes in Computer Science , Vol. 2139 , Joe Kilian (Ed.). Springer , Berlin, 190--200. Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone. 2001. Faster point multiplication on elliptic curves with efficient endomorphisms. In Proceedings of the Conference on Advances in Cryptology (CRYPTO\u201901), Lecture Notes in Computer Science, Vol. 2139, Joe Kilian (Ed.). Springer, Berlin, 190--200."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-014-0090-x"},{"key":"e_1_2_1_23_1","first-page":"21","article-title":"Fast and compact elliptic-curve cryptography","volume":"2012","author":"Hamburg Mike","year":"2012","unstructured":"Mike Hamburg . 2012 . Fast and compact elliptic-curve cryptography . Cryptol. ePrint Arch. 2012 , 309 (2012), 21 . https:\/\/eprint.iacr.org\/2012\/309 Mike Hamburg. 2012. Fast and compact elliptic-curve cryptography. Cryptol. ePrint Arch. 2012, 309 (2012), 21. https:\/\/eprint.iacr.org\/2012\/309","journal-title":"Cryptol. ePrint Arch."},{"key":"e_1_2_1_24_1","first-page":"10","article-title":"Ed448-Goldilocks, a new elliptic curve","volume":"2015","author":"Hamburg Mike","year":"2015","unstructured":"Mike Hamburg . 2015 . Ed448-Goldilocks, a new elliptic curve . Cryptol. ePrint Arch. 2015 , 625 (2015), 10 . https:\/\/eprint.iacr.org\/2015\/625 Mike Hamburg. 2015. Ed448-Goldilocks, a new elliptic curve. Cryptol. ePrint Arch. 2015, 625 (2015), 10. https:\/\/eprint.iacr.org\/2015\/625","journal-title":"Cryptol. ePrint Arch."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89255-7_20"},{"key":"e_1_2_1_27_1","volume-title":"Intel\u00ae 64 and IA-32 Architectures Optimization Reference Manual","author":"Intel Corporation","unstructured":"Intel Corporation . 2009. Intel\u00ae 64 and IA-32 Architectures Optimization Reference Manual . Intel Corporation . Retrieved from http:\/\/www.intel.com\/content\/www\/us\/en\/architecture-and-technology\/64-ia-32-architectures-optimization-manual.html. Intel Corporation. 2009. Intel\u00ae 64 and IA-32 Architectures Optimization Reference Manual. Intel Corporation. Retrieved from http:\/\/www.intel.com\/content\/www\/us\/en\/architecture-and-technology\/64-ia-32-architectures-optimization-manual.html."},{"key":"e_1_2_1_28_1","unstructured":"Intel Corporation. 2011. Intel\u00ae Advanced Vector Extensions Programming Reference. Retrieved from https:\/\/software.intel.com\/sites\/default\/files\/m\/f\/7\/c\/36945.  Intel Corporation. 2011. Intel\u00ae Advanced Vector Extensions Programming Reference. Retrieved from https:\/\/software.intel.com\/sites\/default\/files\/m\/f\/7\/c\/36945."},{"key":"e_1_2_1_29_1","unstructured":"Intel Corporation. 2013. Intel Instruction Set Architecture Extensions. Retrieved from https:\/\/software.intel.com\/en-us\/intel-isa-extensions.  Intel Corporation. 2013. Intel Instruction Set Architecture Extensions. Retrieved from https:\/\/software.intel.com\/en-us\/intel-isa-extensions."},{"key":"e_1_2_1_30_1","volume-title":"Intel\u00ae 64 and IA-32 Architectures Software Developers Manual","author":"Intel Corporation","unstructured":"Intel Corporation . 2014. Intel\u00ae 64 and IA-32 Architectures Software Developers Manual . Intel Corporation , USA. Order Number 253669. Intel Corporation. 2014. Intel\u00ae 64 and IA-32 Architectures Software Developers Manual. Intel Corporation, USA. Order Number 253669."},{"key":"e_1_2_1_31_1","volume-title":"Intel\u00ae Intrinsics Guide. Retrieved","author":"Intel Corporation","year":"2017","unstructured":"Intel Corporation . 2016. Intel\u00ae Intrinsics Guide. Retrieved February 1, 2017 from https:\/\/software.intel.com\/sites\/landingpage\/IntrinsicsGuide\/. Intel Corporation. 2016. Intel\u00ae Intrinsics Guide. Retrieved February 1, 2017 from https:\/\/software.intel.com\/sites\/landingpage\/IntrinsicsGuide\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90024-7"},{"key":"e_1_2_1_33_1","article-title":"Fast elliptic curve multiplications with SIMD operations. IEICE","author":"Izu Tetsuya","year":"2004","unstructured":"Tetsuya Izu and Tsuyoshi Takagi . 2004 . Fast elliptic curve multiplications with SIMD operations. IEICE Trans. Fundam. Electr. Commun. Comput. Sci. 87-A, 1 ( Jan. 2004), 85--93. http:\/\/search.ieice.org\/bin\/summary.php?id&equals;e87-a_1_85 Tetsuya Izu and Tsuyoshi Takagi. 2004. Fast elliptic curve multiplications with SIMD operations. IEICE Trans. Fundam. Electr. Commun. Comput. Sci. 87-A, 1 (Jan. 2004), 85--93. http:\/\/search.ieice.org\/bin\/summary.php?id&equals;e87-a_1_85","journal-title":"Trans. Fundam. Electr. Commun. Comput. Sci. 87-A, 1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Simon Josefsson and Ilari Liusvaara. 2017. Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032.  Simon Josefsson and Ilari Liusvaara. 2017. Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032.","DOI":"10.17487\/RFC8032"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74735-2_10"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70697-9_1"},{"key":"e_1_2_1_37_1","volume-title":"Multiplication of multidigit numbers on automata. Sov. Phys. Dokl. 7 (Jan","author":"Karatsuba Anatolii","year":"1963","unstructured":"Anatolii Karatsuba and Yuri Ofman . 1963. Multiplication of multidigit numbers on automata. Sov. Phys. Dokl. 7 (Jan . 1963 ), 595--596. Anatolii Karatsuba and Yuri Ofman. 1963. Multiplication of multidigit numbers on automata. Sov. Phys. Dokl. 7 (Jan. 1963), 595--596."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/646762.759589"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 6th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-6), Teo Mora (Ed.). Springer","author":"Mastrovito Edoardo D.","year":"1988","unstructured":"Edoardo D. Mastrovito . 1988 . VLSI designs for multiplication over finite fields GF(2<sup>m<\/sup>) . In Proceedings of the 6th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-6), Teo Mora (Ed.). Springer , Berlin, 297--309. Edoardo D. Mastrovito. 1988. VLSI designs for multiplication over finite fields GF(2<sup>m<\/sup>). In Proceedings of the 6th International Conference on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-6), Teo Mora (Ed.). Springer, Berlin, 297--309."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1987-0866113-7"},{"key":"e_1_2_1_41_1","unstructured":"Andrew Moon. 2015. Implementations of a fast Elliptic-curve Diffie-Hellman primitive. Retrieved from https:\/\/github.com\/floodyberry\/curve25519-donna\/tree\/2fe66b65ea1acb788024f40a3373b8b3e6f4bbb2.  Andrew Moon. 2015. Implementations of a fast Elliptic-curve Diffie-Hellman primitive. Retrieved from https:\/\/github.com\/floodyberry\/curve25519-donna\/tree\/2fe66b65ea1acb788024f40a3373b8b3e6f4bbb2."},{"key":"e_1_2_1_42_1","unstructured":"Andrew Moon. 2015. Implementations of a fast Elliptic-curve Digital Signature Algorithm. Retrieved from https:\/\/github.com\/floodyberry\/ed25519-donna\/tree\/8757bd4cd209cb032853ece0ce413f122eef212c.  Andrew Moon. 2015. Implementations of a fast Elliptic-curve Digital Signature Algorithm. Retrieved from https:\/\/github.com\/floodyberry\/ed25519-donna\/tree\/8757bd4cd209cb032853ece0ce413f122eef212c."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-69453-5_6"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-013-0069-z"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72565-9_9"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53140-2_13"},{"key":"e_1_2_1_51_1","volume-title":"New Instructions Supporting Large Integer Arithmetic on Intel\u00ae Architecture Processors","author":"Ozturk Erdinc","unstructured":"Erdinc Ozturk , James Guilford , Vinodh Gopal , and Wajdi Feghali . 2012. New Instructions Supporting Large Integer Arithmetic on Intel\u00ae Architecture Processors . Intel Corporation , White Paper 327831-001. Retrieved from http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/white-papers\/ia-large-integer-arithmetic-paper.pdf. Erdinc Ozturk, James Guilford, Vinodh Gopal, and Wajdi Feghali. 2012. New Instructions Supporting Large Integer Arithmetic on Intel\u00ae Architecture Processors. Intel Corporation, White Paper 327831-001. Retrieved from http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/white-papers\/ia-large-integer-arithmetic-paper.pdf."},{"key":"e_1_2_1_52_1","volume-title":"How to Benchmark Code Execution Times on Intel\u00ae IA-32 and IA-64 Instruction Set Architectures","author":"Paoloni Gabriele","unstructured":"Gabriele Paoloni . 2010. How to Benchmark Code Execution Times on Intel\u00ae IA-32 and IA-64 Instruction Set Architectures . Intel Corporation , White Paper 324264-001. Retrieved from http:\/\/www.intel.com\/content\/www\/us\/en\/embedded\/training\/ia-32-ia-64-benchmark-code-execution-paper.html. Gabriele Paoloni. 2010. How to Benchmark Code Execution Times on Intel\u00ae IA-32 and IA-64 Instruction Set Architectures. Intel Corporation, White Paper 324264-001. Retrieved from http:\/\/www.intel.com\/content\/www\/us\/en\/embedded\/training\/ia-32-ia-64-benchmark-code-execution-paper.html."},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Eric Rescorla. 2018. The Transport Layer Security (TLS) Protocol Version 1.3. RFC 8446.  Eric Rescorla. 2018. The Transport Layer Security (TLS) Protocol Version 1.3. RFC 8446.","DOI":"10.17487\/RFC8446"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008306223194"},{"key":"e_1_2_1_56_1","unstructured":"The OpenSSL Project. 2003. OpenSSL: The Open Source toolkit for SSL\/TLS. Retrieved from https:\/\/www.openssl.org.  The OpenSSL Project. 2003. OpenSSL: The Open Source toolkit for SSL\/TLS. Retrieved from https:\/\/www.openssl.org."},{"key":"e_1_2_1_57_1","unstructured":"Sean Turner Adam Langley and Mike Hamburg. 2016. Elliptic Curves for Security. RFC 7748.  Sean Turner Adam Langley and Mike Hamburg. 2016. Elliptic Curves for Security. RFC 7748."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:36Z","timestamp":1750204416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,30]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3309759"],"URL":"https:\/\/doi.org\/10.1145\/3309759","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,30]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}