International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography on x86-64 based Processors

Catherine Gebotys
Patrick Longa
Search ePrint
Search Google
Abstract: In this work, we analyze and present experimental data evaluating the efficiency of several techniques for speeding up the computation of elliptic curve point multiplication on emerging x86-64 processor architectures. In particular, we study the efficient combination of such techniques as elimination of conditional branches and incomplete reduction to achieve fast field arithmetic over GF(p). Furthermore, we study the impact of (true) data dependencies on these processors and propose several generic techniques to reduce the number of pipeline stalls, memory reads/writes and function calls. We also extend these techniques to field arithmetic over GF(p^2), which is utilized as underlying field by the recently proposed Galbraith-Lin-Scott (GLS) method to achieve higher performance in the point multiplication. By efficiently combining all these methods with state-of-the-art elliptic curve algorithms we obtain high-speed implementations of point multiplication that are up to 31% faster than the best previous published results on similar platforms. This research is crucial for advancing high-speed cryptography on new emerging processor architectures.
  title={Analysis of Efficient Techniques for Fast Elliptic Curve Cryptography  on x86-64 based Processors},
  booktitle={IACR Eprint archive},
  keywords={Implementation / Elliptic curve cryptosystem, point multiplication, field arithmetic scheduling, incomplete reduction, data dependence, pipeline stall, x86-64 instruction set, software implementation.},
  note={ 14769 received 8 Jun 2010, last revised 9 Jun 2010},
  author={Catherine Gebotys and Patrick Longa},