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$.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
finite fieldspairing-based cryptographyelliptic curves of $j$-invariant $1728$Kummer surfacesrational curvesWeil restrictionisogenies
Contact author(s)
dishport @ ya ru
History
2021-06-21: last of 12 revisions
2019-11-07: received
See all versions
Short URL
https://ia.cr/2019/1294
License
Creative Commons Attribution
CC BY

BibTeX

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