phd_libs
High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves
Supporting Material of PhD Thesis authored by Armando Faz Hernandez at the Institute of Computing of the University of Campinas
Full Text: https://hdl.handle.net/20.500.12733/6756
| Awards | How to Cite | Software Libraries |
|---|
Content
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.
See full abstract
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.
Awards
- Prêmio Melhor Tese de Doutorado 2022 -- Instituto de Computação. https://ic.unicamp.br/noticia/9658/cerimonia-de-premiacao-interna-do-ic-referente-ao-ano-de-2022/
- 1er Prêmio Tese Destaque Unicamp 2022 -- Universidade Estadual de Campinas. https://www.prpg.unicamp.br/noticias/a-prpg-divulga-o-resultado-do-premio-tese-destaque-unicamp-2022/
- Honorific Mention at SBSeg 2024 https://sbseg2024.ita.br/premiacoes/.
- Finalist at the 36th Thesis and Dissertation Contest organized by the Congress of the Brazilian Computing Society (CSBC 2023) https://csbc.sbc.org.br/2023/ctd/.
- Honorific Mention -- SBSeg2016 Best Paper Award to "Speeding up the Elliptic Curve Cryptography on the P-384 Curve" article http://sbseg2016.ic.uff.br/pt/trabalhos-premiados.php
Software Libraries
We develop a set of software libraries that show implementation techniques and optimizations of several cryptographic algorithms. Our libraries are available at public repositories released under permissive software licenses, and are also available at an institutional repository:
Homepage: https://gitlab.ic.unicamp.br/ra142685/phd_libs
fld-ecc-vec
An optimized implementation of the Ed25519 and Ed448 signature schemes, the X25519 and X448 Diffie-Hellman protocols, and hash to curve functions using AVX2 vector instructions.
flor-sidh-x64
An implementation of the SIDH-751 Diffie-Hellman protocol accelerated with BMI2 and ADX instructions.
rfc7748_precomputed
An optimized 64-bit implementation of the X25519 and X448 Diffie-Hellman protocols accelerated with BMI2 and ADX instructions.
nistp384_avx2
A SIMD implementation of the complete addition formulas for the P-384 Weierstrass curve.
qdsa_space2017
An optimized 64-bit implementation of the qDSA signature scheme.
flo-shani-aesni
Optimized implementations of SHA-256 using SHANI instructions, and AES and AEGIS using AESNI instructions.
How to Cite
@phdthesis{armfazhPhD,
author = "Armando Faz-Hernandez",
title = "High-Performance Elliptic Curve Cryptography: A SIMD Approach to Modern Curves",
school = "University of Campinas",
year = "2022",
type = "stricto sensu",
address = "Campinas, Brazil",
month = "sep",
url = "https://hdl.handle.net/20.500.12733/6756",
}