[Resource Topic] 2021/1604: The most efficient indifferentiable hashing to elliptic curves of $j$-invariant $1728$

Welcome to the resource topic for 2021/1604

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

Authors: Dmitrii Koshelev


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.

ePrint: https://eprint.iacr.org/2021/1604

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .