Cryptology ePrint Archive: Report 2021/1604

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:

[ Cryptology ePrint archive ]