Paper 2021/1604

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

Abstract

This article makes an important contribution to solving the long-standing problem of whether all elliptic curves can be equipped with a hash function (indifferentiable from a random oracle) whose running time amounts to one exponentiation in the basic finite field $\mathbb{F}_{\!q}$. More precisely, we construct a new indifferentiable hash function to any ordinary elliptic $\mathbb{F}_{\!q}$-curve $E_a$ of $j$-invariant $1728$ with the cost of extracting one quartic root in $\mathbb{F}_{\!q}$. As is known, the latter operation is equivalent to one exponentiation in finite fields with which we deal in practice. In comparison, the previous fastest random oracles to $E_a$ require to perform two exponentiations in $\mathbb{F}_{\!q}$. 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 new result seems to be unimprovable.