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
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.
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.
ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. pages 10–18.
Faz-Hernandez, 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.
IEEE (2000). IEEE Standard Specifications for Public-Key Cryptography. DOI: 10.1109/IEEESTD.2000.92292.
Intel Corporation (2011). Intrinsics for Intel Advanced Vector Extensions. [link].
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 (2023). Digital Signature Standard (DSS). Technical Report FIPS PUB 186-5, National Institute of Standards and Technology. DOI: 10.6028/NIST.FIPS.186-5.
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. DOI: 10.1109/2.809248.
