International Association
for Cryptologic Research

This paper establishes that the extended Euclidean algorithm (EEA) implemented in a division-free manner is faster than the Lagrange algorithm with a similar level of optimization when it comes to halving the size of scalars found in the equations of elliptic curve signature verification. Our implementation results show that our EEA based method achieves roughly 4x speed-up for generating half- size scalars used in EdDSA. For the first time ever, EEA generated half-size scalars are used for verification of individual Ed25519 signatures yielding timing results that outperform ed25519-donna, a highly optimized open source implementation, by 16.12%. We also propose a new randomization method applied with half-size scalars to batch verification of Ed25519 signatures for which we report speed-ups compared to the well-known Bernstein et al. method for batch sizes larger than six, specifically, our method achieves 11.60% improvement for batch size 64.

Strategies and their evaluations play important roles in speeding up the computation of large smooth-degree isogenies. The concept of optimal strategies for such computation was introduced by De Feo et al., and virtually all implementations of isogeny-based protocols have adopted this approach, which is provably optimal for single-core platforms. In spite of its inherent sequential nature, several recent works have studied ways of speeding up this isogeny computation by exploiting the rich parallelism available in vectorized and multi-core platforms. One obstacle to taking full advantage of this parallelism, however, is that De Feo et al.’s strategies are not necessarily optimal in multi-core environments. To illustrate how the speed of vectorized and parallel isogeny computation can be improved at the strategylevel, we present two novel software implementations that utilize a state-of-the-art evaluation technique, called precedence-constrained scheduling (PCS), presented by Phalakarn et al., with our proposed strategies crafted for these environments. Our first implementation relies only on the parallelism provided by multi-core processors. The second implementation targets multi-core processors supporting the latest generation of the Intel’s Advanced Vector eXtensions (AVX) technology, commonly known as AVX-512IFMA instructions. To better handle the computational concurrency associated with PCS, we equip both implementations with extensive synchronization techniques. Our first implementation outperforms the implementation of Cervantes-Vázquez et al. by yielding up to 14.36% reduction in the execution time, when targeting platforms with two- to four-core processors. Our second implementation, equipped with four cores, achieves up to 34.05% reduction in the execution time compared to the single-core implementation of Cheng et al. of CHES 2022.