Cryptology ePrint Archive: Report 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}$.

Category / Keywords: implementation / congruent elliptic curves, encodings to (hyper)elliptic curves, isogenies, $j$-invariants $0$, $1728$, median value curves, optimal covers, Weil pairing

Date: received 8 Aug 2021, last revised 16 Aug 2021

Contact author: dimitri koshelev at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210816:140205 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]