Paper 2021/1034

Optimal encodings to elliptic curves of $j$-invariants $0$, $1728$

Dmitrii Koshelev

Abstract

This article provides new constant-time encodings $\mathbb{F}_{\!q}^* \to E(\mathbb{F}_{\!q})$ to ordinary elliptic $\mathbb{F}_{\!q}$-curves $E$ of $j$-invariants $0$, $1728$ having a small prime divisor of the Frobenius trace. Therefore all curves of $j = 1728$ are covered. This is also true for the Barreto--Naehrig curves BN512, BN638 from the international cryptographic standards ISO/IEC 15946-5, TCG Algorithm Registry, and FIDO ECDAA Algorithm. Many $j = 1728$ curves as well as BN512, BN638 are not appropriate for the most efficient prior encodings. So, in fact, only universal SW (Shallue--van de Woestijne) one was previously applicable to them. However this encoding (in contrast to ours) can not be computed at the cost of one exponentiation in the field $\mathbb{F}_{\!q}$.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
congruent elliptic curvesencodings to (hyper)elliptic curvesisogenies$j$-invariants $0$$1728$median value curvesoptimal coversWeil pairing
Contact author(s)
dimitri koshelev @ gmail com
History
2022-02-04: last of 2 revisions
2021-08-16: received
See all versions
Short URL
https://ia.cr/2021/1034
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1034,
      author = {Dmitrii Koshelev},
      title = {Optimal encodings to elliptic curves of $j$-invariants $0$, $1728$},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1034},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1034}},
      url = {https://eprint.iacr.org/2021/1034}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.