### Efficient and Complete Formulas for Binary Curves

##### Abstract

Binary elliptic curves are elliptic curves defined over finite fields of characteristic 2. On software platforms that offer carryless multiplication opcodes (e.g. pclmul on x86), they have very good performance. However, they suffer from some drawbacks, in particular that non-supersingular binary curves have an even order, and that most known formulas for point operations have exceptional cases that are detrimental to safe implementation. In this paper, we show how to make a prime order group abstraction out of standard binary curves. We describe a new canonical compression scheme that yields a canonical and compact encoding. We also describe complete formulas for operations on the group. The formulas have no exceptional case, and are furthermore faster than previously known complete and incomplete formulas (general point addition in cost 8M+2S+2mb on all curves, 7M+2S+2mb on half of the curves). We also show how the same formulas can be applied to computations on the entire original curve, if full backward compatibility with standard curves is needed. Finally, we implemented our method over the standard NIST curves B-233 and K-233. Our strictly constant-time code achieves generic point multiplication by a scalar on curve K-233 in as little as 29600 clock cycles on an Intel x86 CPU (Coffee Lake core).

##### Metadata
Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
binary elliptic curves complete formulas K-233
Contact author(s)
thomas pornin @ nccgroup com
History
2022-10-05: approved
2022-10-05: received
See all versions
Short URL
https://ia.cr/2022/1325
License

CC BY

BibTeX

@misc{cryptoeprint:2022/1325,
author = {Thomas Pornin},
title = {Efficient and Complete Formulas for Binary Curves},
howpublished = {Cryptology ePrint Archive, Paper 2022/1325},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1325}},
url = {https://eprint.iacr.org/2022/1325}
}

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