The most efficient indifferentiable hashing to elliptic curves of j -invariant 1728
Dmitrii Koshelev · Journal of Mathematical Cryptology · 2022
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 F q {{\mathbb{F}}}_{q} . More precisely, we construct a new indifferentiable hash function to any ordinary elliptic F q {{\mathbb{F}}}_{q} -curve E a {E}_{a} of j -invariant 1728 with the cost of extracting one quartic root in F q {{\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 {E}_{a} require to perform two exponentiations in F q {{\mathbb{F}}}_{q} . Since it is highly unlikely that there is a hash function to an elliptic curve without any exponentiations at all (even if it is supersingular), the new result seems to be unimprovable.