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