Paper 2021/383

GLV+HWCD for 2y^2=x^3+x/GF(8^91+5)

Daniel R. L. Brown

Abstract

This report considers combining three well-known optimization methods for elliptic curve scalar multiplication: Gallant--Lambert--Vanstone (GLV) for complex multiplication endomorphisms $[i]$ and $[i+1]$; 3-bit fixed windows (signed base 8); and Hisil--Wong--Carter--Dawson (HWCD) curve arithmetic for twisted Edwards curves. An $x$-only Diffie--Hellman scalar multiplication for curve $2y^2=x^3+x$ over field size $8^{91}+5$ has arithmetic cost $947\textbf{M} + 1086\textbf{S}$, where $\textbf{M}$ is a field multiplication and $\textbf{S}$ is a field squaring. This is approximately $(3.55\textbf{M} + 4.07\textbf{S})$/bit, with $1\textbf{S}$/bit for input decompression and $1\textbf{S}$/bit for output normalization. Optimizing speed by allowing uncompressed input points leads to an estimate $(3.38\textbf{M}+2.95\textbf{S})$/bit. To mitigate some side-channel attacks, the secret scalar is only used to copy curve points from one array to another: the field operations used are fixed and independent of the secret scalar. The method is likely vulnerable to cache-timing attacks, nonetheless.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
elliptic curve cryptosystem
Contact author(s)
danibrown @ blackberry com
History
2021-03-27: received
Short URL
https://ia.cr/2021/383
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/383,
      author = {Daniel R.  L.  Brown},
      title = {GLV+HWCD for 2y^2=x^3+x/GF(8^91+5)},
      howpublished = {Cryptology ePrint Archive, Paper 2021/383},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/383}},
      url = {https://eprint.iacr.org/2021/383}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.