International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Trading Inversions for Multiplications in Elliptic Curve Cryptography

Authors:
Mathieu Ciet
Marc Joye
Kristin E. Lauter
Peter L. Montgomery
Download:
URL: http://eprint.iacr.org/2003/257
Search ePrint
Search Google
Abstract: Recently, Eisentraeger-Lauter-Montgomery proposed a method for speeding up scalar multiplication on elliptic curves. That method relies on improved formulae for evaluating S = 2P + Q from given points P and Q on an elliptic curve. Compared to the naive approach, the improved formulae save a field multiplication each time the operation is performed. This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling or quadrupling a point, and present a ternary/binary method to perform efficient scalar multiplication.
BibTeX
@misc{eprint-2003-11970,
  title={Trading Inversions for Multiplications in Elliptic Curve Cryptography},
  booktitle={IACR Eprint archive},
  keywords={implementation / elliptic curve cryptosystem},
  url={http://eprint.iacr.org/2003/257},
  note={accepted for publication in Designs, Codes, and Cryptography klauter@microsoft.com 12951 received 16 Dec 2003, last revised 16 Jun 2005},
  author={Mathieu Ciet and Marc Joye and Kristin E. Lauter and Peter L. Montgomery},
  year=2003
}