Cryptology ePrint Archive: Report 2003/257

Trading Inversions for Multiplications in Elliptic Curve Cryptography

Mathieu Ciet and Marc Joye and Kristin Lauter and Peter L. Montgomery

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.

Category / Keywords: implementation / elliptic curve cryptosystem

Publication Info: accepted for publication in Designs, Codes, and Cryptography

Date: received 16 Dec 2003, last revised 16 Jun 2005

Contact author: klauter at microsoft com

Available format(s): PDF | BibTeX Citation

Note: minor changes throughout

Version: 20050617:000431 (All versions of this report)

Short URL: ia.cr/2003/257

Discussion forum: Show discussion | Start new discussion