### Double-Odd Elliptic Curves

Thomas Pornin

##### Abstract

This article explores the use of elliptic curves with order 2r = 2 mod 4, which we call double-odd elliptic curves. This is a very large class, comprising about 1/4th of all curves over a given field. On such curves, we manage to define a prime order group with appropriate characteristics for building cryptographic protocols: - Element encoding is canonical, and verified upon decoding. For a 2n-bit group (with n-bit security), encoding size is 2n + 1 bits, i.e. as good as compressed points on classic prime order curves. - Unified and complete formulas allow secure and efficient computations in the group. - Efficiency is on par with twisted Edwards curves, and in some respects slightly better; e.g. half of double-odd curves have formulas for computing point doublings with only six multiplications (down to 1M+5S per doubling on some curves). We describe here various formulas and discuss implementations. We also define two specific parameter choices for curves with 128-bit security, called do255e and do255s. Our own implementations on 64-bit x86 (Coffee Lake) and low-end ARM Cortex M0+ achieve generic point multiplication in 76696 and 2.19 million cycles, respectively, with curve do255e.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve cryptosystemsdouble-odd curves
Contact author(s)
thomas pornin @ nccgroup com
History
Short URL
https://ia.cr/2020/1558

CC BY

BibTeX

@misc{cryptoeprint:2020/1558,
author = {Thomas Pornin},
title = {Double-Odd Elliptic Curves},
howpublished = {Cryptology ePrint Archive, Paper 2020/1558},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1558}},
url = {https://eprint.iacr.org/2020/1558}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.