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 do not have $\mathbb{F}_{\!q}$-isogenies of small degree from other elliptic curves. So, in fact, only universal SW (Shallue--van de Woestijne) encoding 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)
- 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-11-16: last of 4 revisions
- 2021-08-16: received
- See all versions
- Short URL
- https://ia.cr/2021/1034
- License
-
CC BY