High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves
Resumo
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.
Referências
ARM. ARM NEON Intrinsics. [link].
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, pages 389–405. Springer Berlin Heidelberg.
Bernstein, D. J. and Lange, T. (2015). SafeCurves: choosing safe curves for elliptic-curve cryptography. [link] accessed 20 March 2015.
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, pages 303–329, Cham. Springer International Publishing.
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, pages 572–601, Berlin, Heidelberg. Springer Berlin Heidelberg.
Diffie, W. and Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654.
Donenfeld, J. A. (2018). Wireguard Linux Compat. Patch to Wireguard: [link].
ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. pages 10–18.
Faz-Hernández, A. (2022). High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves. PhD thesis, University of Campinas, Campinas, Brazil. [link].
Flynn, M. (1966). Very high-speed computing systems. Proceedings of the IEEE, 54(12):1901–1909.
Gueron, S. (2009). Intel’s New AES Instructions for Enhanced Performance and Security. In Dunkelman, O., editor, Fast Software Encryption: 16th International Workshop, FSE 2009 Leuven, Belgium, February 22-25, 2009 Revised Selected Papers, pages 51–66, Berlin, Heidelberg. Springer.
IEEE (2000). IEEE Standard Specifications for Public-Key Cryptography. https://doi.org/10.1109/IEEESTD.2000.92292.
Intel Corporation (2011). Intel® Advanced Vector Extensions Programming Reference. [link].
Jao, D., Azarderakhsh, R., Campagna, M., Costello, C., Feo, L. D., Hess, B., Jalali, A., Koziel, B., LaMacchia, B., Longa, P., Naehrig, M., Renes, J., Soukharev, V., Urbanik, D., and Pereira, G. (2017). Supersingular Isogeny Key Encapsulation.
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.
Montgomery, P. L. (1987). Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation, 48(177):243–264.
NIST (2000). Digital Signature Standard (DSS). Technical report, National Institute of Standards and Technology. [link].
NIST (2016). Post-Quantum Cryptography Standardization. National Institute of Standards and Technology. [link].
NIST (2023). Digital Signature Standard (DSS). Technical Report FIPS PUB 186-5, National Institute of Standards and Technology. https://doi.org/10.6028/NIST.FIPS.186-5.
Protzenko, J., Parno, B., Fromherz, A., Hawblitzel, C., Polubelova, M., Bhargavan, K., Beurdouche, B., Choi, J., Delignat-Lavaud, A., Fournet, C., Kulatova, N., Ramananandro, T., Rastogi, A., Swamy, N., Wintersteiger, C. M., and Zanella-Beguelin, S. (2020).
EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider. In 2020 IEEE Symposium on Security and Privacy (SP), pages 983–1002.
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.
Thakkar, S. and Huff, T. (1999). Internet Streaming SIMD Extensions. Computer, 32(12):26–34. http://doi.org/10.1109/2.809248.
