Paper 2019/1294

Hashing to elliptic curves of $j$-invariant $1728$

Dmitrii Koshelev

Abstract

This article generalizes the simplified Shallue--van de Woestijne--Ulas (SWU) method of a deterministic finite field mapping $h:{\mathbb{F}}_q\to E_a({\mathbb{F}}_q)$ to the case of any elliptic ${\mathbb{F}}_q$-curve $E_a:y^2=x^3-ax$ of $j$-invariant $1728$. In comparison with the (classical) SWU method the simplified SWU method allows to avoid one quadratic residuosity test in the field ${\mathbb{F}}_q$, which is a quite painful operation in cryptography with regard to timing attacks. More precisely, in order to derive $h$ we obtain a rational ${\mathbb{F}}_q$-curve $C$ (and its explicit quite simple proper ${\mathbb{F}}_q$-parametrization) on the Kummer surface $K^{\prime }$ associated with the direct product $E_a\times E_a^{\prime }$, where $E_a^{\prime }$ is the quadratic ${\mathbb{F}}_q$-twist of $E_a$. Our approach of finding $C$ is based on the fact that every curve $E_a$ has a vertical ${\mathbb{F}}_{q^2}$-isogeny of degree $2$.