Paper 2021/1034

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

Abstract

This article provides new constant-time encodings ${\mathbb{F}}_q^{\ast }\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 circumstance 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 the new ones) cannot be computed at the cost of one exponentiation in the field ${\mathbb{F}}_q$.