Paper 2015/1060
Complete addition formulas for prime order elliptic curves
Joost Renes, Craig Costello, and Lejla Batina
Abstract
An elliptic curve addition law is said to be complete if it correctly computes the sum of any two points in the elliptic curve group. One of the main reasons for the increased popularity of Edwards curves in the ECC community is that they can allow a complete group law that is also relatively efficient (e.g., when compared to all known addition laws on Edwards curves). Such complete addition formulas can simplify the task of an ECC implementer and, at the same time, can greatly reduce the potential vulnerabilities of a cryptosystem. Unfortunately, until now, complete addition laws that are relatively efficient have only been proposed on curves of composite order and have thus been incompatible with all of the currently standardized prime order curves. In this paper we present optimized addition formulas that are complete on every prime order short Weierstrass curve defined over a field k with char(k) not 2 or 3. Compared to their incomplete counterparts, these formulas require a larger number of field additions, but interestingly require fewer field multiplications. We discuss how these formulas can be used to achieve secure, exception-free implementations on all of the prime order curves in the NIST (and many other) standards.
Note: EUROCRYPT 2016 camera-ready version
Metadata
- Available format(s)
-
👁 Image
PDF - Category
- Public-key cryptography
- Publication info
- Published by the IACR in EUROCRYPT 2016
- Keywords
- public-key cryptographyelliptic curvesshort Weierstrass formcomplete addition formulas
- Contact author(s)
- j renes @ cs ru nl
- History
- 2016-03-08: revised
- 2015-10-30: received
- See all versions
- Short URL
- https://ia.cr/2015/1060
- License
-
👁 Creative Commons Attribution
CC BY
BibTeX
@misc{cryptoeprint:2015/1060,
author = {Joost Renes and Craig Costello and Lejla Batina},
title = {Complete addition formulas for prime order elliptic curves},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/1060},
year = {2015},
url = {https://eprint.iacr.org/2015/1060}
}
