High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves (Thesis Distillation)

Armando Faz-Hernandez; Julio López

doi:10.5753/jbcs.2026.5548

Authors

Armando Faz-Hernandez University of Campinas https://orcid.org/0000-0001-5502-8666
Julio López University of Campinas https://orcid.org/0000-0001-5139-0158

DOI:

https://doi.org/10.5753/jbcs.2026.5548

Keywords:

Cryptography, Elliptic Curves, Parallel Computing, SIMD, Diffie-Hellman, Digital Signatures

Abstract

Cryptography based on elliptic curves is endowed with efficient methods for public-key cryptography. Recent research has shown the superiority of the Montgomery and Edwards curves over the Weierstrass curves as they require fewer arithmetic operations. Using these modern curves has, however, introduced several challenges to the cryptographic algorithm's design, opening up new opportunities for optimization. Our main objective is to propose algorithmic optimizations and implementation techniques for cryptographic algorithms based on elliptic curves. In order to speed up the execution of these algorithms, our approach relies on the use of extensions to the instruction set architecture. In addition to those specific for cryptography, we use extensions that follow the Single Instruction, Multiple Data (SIMD) parallel computing paradigm. In this model, the processor executes the same operation over a set of data in parallel. We investigated how to apply SIMD to the implementation of elliptic curve algorithms. As part of our contributions, we design parallel algorithms for prime field and elliptic curve arithmetic. We also design a new three-point ladder algorithm for the scalar multiplication P+kQ, and a faster formula for calculating 3P on Montgomery curves. These algorithms have found applicability in isogeny-based cryptography. Using SIMD extensions such as SSE, AVX, and AVX2, we develop optimized implementations of the following cryptographic algorithms: X25519, X448, SIDH, ECDH, ECDSA, EdDSA, and qDSA. Performance benchmarks show that these implementations are faster than existing implementations in the state of the art. Our study confirms that using extensions to the instruction set architecture is an effective tool for optimizing implementations of cryptographic algorithms based on elliptic curves. May this be an incentive not only for those seeking to speed up programs in general but also for computer manufacturers to include more advanced extensions that support the increasing demand for cryptography.

Downloads

Download data is not yet available.

References

Aardal, M. A., Adj, G., Alblooshi, A., Aranha, D. F., Canales-Martínez, I. A., Chávez-Saab, J., Gazzoni Filho, D. L., Reijnders, K., and Rodríguez-Henríquez, F. (2024). Optimized One-Dimensional SQIsign Verification on Intel and Cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(1):497–522. DOI: 10.46586/tches.v2025.i1.497-522.

Abdalla, M., Bellare, M., and Rogaway, P. (1999). DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem. Available at: [link].

ANSI (1998). Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). Technical Report ANSI X9.62-1998, American National Standards Institute. Available at: [link].

Barnes, R., Bhargavan, K., Lipp, B., and Wood, C. A. (2022). Hybrid Public Key Encryption. The RFC Series. RFC 9180. DOI: 10.17487/RFC9180.

Bellare, M. and Rogaway, P. (1997). Minimizing the Use of Random Oracles in Authenticated Encryption Schemes. In Proceedings of the First International Conference on Information and Communication Security, ICICS '97, page 1–16, London, UK, UK. Springer-Verlag. DOI: 10.1007/BFb0028457.

Bernstein, D. J., Birkner, P., Joye, M., Lange, T., and Peters, C. (2008). Twisted Edwards Curves. In Vaudenay, S., editor, Progress in Cryptology – AFRICACRYPT 2008, volume 5023 of Lecture Notes in Computer Science, page 389–405. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-68164-9_26.

Bernstein, D. J. and Lange, T. (2015). SafeCurves: choosing safe curves for elliptic-curve cryptography. Available at: [link] Accessed 20 March 2015.

Brier, E., Coron, J.-S., Icart, T., Madore, D., Randriam, H., and Tibouchi, M. (2010). Efficient Indifferentiable Hashing into Ordinary Elliptic Curves. In Rabin, T., editor, Advances in Cryptology – CRYPTO 2010, volume 6223, page 237–254. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-14623-7_13.

Chou, T. (2016). Sandy2x: New Curve25519 Speed Records. In Dunkelman, O. and Keliher, L., editors, Selected Areas in Cryptography – SAC 2015, page 145–160, Cham. Springer International Publishing. DOI: 10.1007/978-3-319-31301-6_8.

Cooper, D., Apon, D., Dang, Q., Davidson, M., Dworkin, M., and Miller, C. (2020). Recommendation for Stateful Hash-Based Signature Schemes. (NIST SP 800-208). DOI: 10.6028/NIST.SP.800-208.

Costello, C. and Hisil, H. (2017). A Simple and Compact Algorithm for SIDH with Arbitrary Degree Isogenies. In Takagi, T. and Peyrin, T., editors, Advances in Cryptology – ASIACRYPT 2017, page 303–329, Cham. Springer International Publishing. DOI: 10.1007/978-3-319-70697-9_11.

Costello, C., Longa, P., and Naehrig, M. (2016). Efficient Algorithms for Supersingular Isogeny Diffie-Hellman. In Robshaw, M. and Katz, J., editors, Advances in Cryptology – CRYPTO 2016, page 572–601, Berlin, Heidelberg. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-53018-4_21.

De Feo, L., Kohel, D., Leroux, A., Petit, C., and Wesolowski, B. (2020). SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. In Moriai, S. and Wang, H., editors, Advances in Cryptology – ASIACRYPT 2020, page 64–93, Cham. Springer International Publishing. DOI: 10.1007/978-3-030-64837-4_3.

Edwards, H. M. (2007). A normal form for elliptic curves. Bulletin of the American Mathematical Society, 44(3):393–422. DOI: 10.1090/S0273-0979-07-01153-6.

ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Blakley, G. R. and Chaum, D., editors, Advances in Cryptology. CRYPTO 1984, page 10–18, Berlin, Heidelberg. Springer Berlin Heidelberg. DOI: 10.1007/3-540-39568-7_2.

Faz-Hernandez, A. (2022). High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves. PhD thesis, University of Campinas, Campinas, Brazil. Available at: [link].

Faz-Hernandez, A. and López, J. (2024). High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves (Extended Thesis Summary). CLEI Electronic Journal, 27(3):1–8. DOI: 10.19153/cleiej.27.3.3.

Faz-Hernandez, A., López, J., and de Oliveira, A. K. D. S. (2018). SoK: A Performance Evaluation of Cryptographic Instruction Sets on Modern Architectures. In Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop, APKC '18, page 9–18, New York, NY, USA. ACM. DOI: 10.1145/3197507.3197511.

Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., and Wood, C. A. (2023). Hashing to Elliptic Curves. The RFC Series. RFC 9380. DOI: 10.17487/RFC9380.

Faz-Hernández, A., Fujii, H., Aranha, D. F., and López, J. (2017). A Secure and Efficient Implementation of the Quotient Digital Signature Algorithm (qDSA). In Ali, S. S., Danger, J.-L., and Eisenbarth, T., editors, Security, Privacy, and Applied Cryptography Engineering, page 170–189, Cham. Springer International Publishing. DOI: 10.1007/978-3-319-71501-8_10.

Faz-Hernández, A. and López, J. (2015). Fast Implementation of Curve25519 Using AVX2. In Lauter, K. and Rodríguez-Henríquez, F., editors, Progress in Cryptology – LATINCRYPT 2015, volume 9230 of Lecture Notes in Computer Science, page 329–345. Springer International Publishing. DOI: 10.1007/978-3-319-22174-8_18.

Faz-Hernández, A. and López, J. (2016). Speeding up Elliptic Curve Cryptography on the P-384 Curve. In XVI Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, volume 16, page 170–183. Sociedade Brasileira de Computação – SBC. DOI: 10.5753/sbseg.2016.19306.

Faz-Hernández, A. and López, J. (2020). Generation of Elliptic Curve Points in Tandem. In Moraes, I. M. and Kowada, L., editors, XX Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, volume 20, page 1–9, Petrópolis, RJ, Brasil. Sociedade Brasileira de Computação. DOI: 10.5753/sbseg.2020.19230.

Faz-Hernández, A., López, J., and Dahab, R. (2019). High-performance Implementation of Elliptic Curve Cryptography Using Vector Instructions. ACM Transactions on Mathematical Software (TOMS), 45(3):1–35. DOI: 10.1145/3309759.

Faz-Hernández, A., López, J., Ochoa-Jiménez, E., and Rodríguez-Henríquez, F. (2018). A Faster Software Implementation of the Supersingular Isogeny Diffie-Hellman Key Exchange Protocol. IEEE Transactions on Computers, 67(11):1622–1636. DOI: 10.1109/TC.2017.2771535.

Flynn, M. (1966). Very high-speed computing systems. Proceedings of the IEEE, 54(12):1901–1909. DOI: 10.1109/PROC.1966.5273.

Gulley, S., Gopal, V., Yap, K., Feghali, W., Gullford, J., and Wolrich, G. (2013). Intel ® SHA Extensions New Instructions Supporting the Secure Hash Algorithm on Intel ® Architecture Processors. Technical report, Intel Corporation. Available at: [link].

Huelsing, A., Butin, D., Gazdag, S.-L., Rijneveld, J., and Mohaisen, A. (2018). XMSS: eXtended Merkle Signature Scheme. The RFC Series. RFC 8391. DOI: 10.17487/RFC8391.

IEEE (2000). IEEE Standard Specifications for Public-Key Cryptography. IEEE Std 1363, page 1–228. DOI: 10.1109/IEEESTD.2000.92292.

Intel Corporation (2011). Intrinsics for Intel Advanced Vector Extensions. Available at: [link].

Intel Corporation (2018). The Intel® Advanced Vector Extensions 512 (Intel® AVX-512) Vector Length Extensions Feature on Intel® Xeon® Scalable Processors. Available at: [link].

Jao, D. and De Feo, L. (2011). Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. In Yang, B.-Y., editor, Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 – December 2, 2011. Proceedings, page 19–34, Berlin, Heidelberg. Springer. DOI: 10.1007/978-3-642-25405-5_2.

Jao, D., De Feo, L., and Plût, J. (2014). Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. Journal of Mathematical Cryptology, 8(3):209–247. DOI: 10.1007/978-3-642-25405-5_2.

Montgomery, P. L. (1987). Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation, 48(177):243–264. DOI: 10.1090/S0025-5718-1987-0866113-7.

Moon, A. (2012). Implementations of a fast Elliptic-curve Diffie-Hellman primitive. Available at: [link].

NIST (2000). Digital Signature Standard (DSS). Technical Report FIPS PUB 186-2, National Institute of Standards and Technology. Available at: [link].

NIST (2023). Digital Signature Standard (DSS). (FIPS PUB 186-5):86. DOI: 10.6028/NIST.FIPS.186-5.

NIST (2024). Post-Quantum Cryptography: Additional Digital Signature Schemes. National Institute of Standards and Technology. Available at: [link].

Oliveira, T., López, J., Hışıl, H., Faz-Hernández, A., and Rodríguez-Henríquez, F. (2018). How to (Pre-)Compute a Ladder. In Adams, C. and Camenisch, J., editors, Selected Areas in Cryptography – SAC 2017, page 172–191, Cham. Springer International Publishing. DOI: 10.1007/978-3-319-72565-9_9.

Renes, J. and Smith, B. (2017). qDSA: Small and Secure Digital Signatures with Curve-Based Diffie–Hellman Key Pairs. In Takagi, T. and Peyrin, T., editors, Advances in Cryptology – ASIACRYPT 2017, page 273–302, Cham. Springer International Publishing. DOI: 10.1007/978-3-319-70697-9_10.

Rivest, R. L., Shamir, A., and Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Commun. ACM, 21(2):120–126. DOI: 10.1145/359340.359342.

Thakkar, S. and Huff, T. (1999). Internet Streaming SIMD Extensions. Computer, 32(12):26–34. DOI: 10.1109/2.809248.

Velú, J. (1971). Isogénies entre courbes elliptiques. Comptes rendus de l’Académie des Sciences de Paris, 273:238–241. Available at: [link].