**The most efficient indifferentiable hashing to elliptic curves of $j$-invariant $1728$**

*Dmitrii Koshelev*

**Abstract: **This article contains a new hash function (indifferentiable from a random oracle) to any ordinary elliptic curve $E_a\!: y^2 = x^3 + ax$ (of invariant $1728$) over a finite field $\mathbb{F}_{\!q}$. Its advantage consists in the necessity to compute (in constant time) only one exponentiation in $\mathbb{F}_{\!q}$, at least for the most practical case $q \equiv 5 \ (\mathrm{mod} \ 8)$. In comparison, for such a $q$ the previous fastest constant-time indifferentiable hash functions to $E_a$ require to compute two exponentiations in $\mathbb{F}_{\!q}$. By the way, the famous Shallue--van de Woestijne hash function (acting as a random oracle) performs four exponentiations in $\mathbb{F}_{\!q}$ even when it is implemented as efficiently as possible. Since it is highly unlikely that there is a hash function to an elliptic curve without exponentiations at all (even if it is supersingular), the result of the given article seems to be unimprovable.

**Category / Keywords: **implementation / Calabi--Yau threefolds, double-odd elliptic curves, elliptic fibrations, indifferentiable hashing to elliptic curves, $j$-invariant $1728$, pairing-based cryptography, quartic residue symbol and quartic roots, rational surfaces, Weil--Aubry--Perret inequality

**Date: **received 8 Dec 2021, last revised 30 Dec 2021

**Contact author: **dimitri koshelev at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20211230:094102 (All versions of this report)

**Short URL: **ia.cr/2021/1604

[ Cryptology ePrint archive ]