Paper 2021/1604

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

Dmitrii Koshelev
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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Calabi--Yau threefolds double-odd curves indifferentiable hashing $j$-invariant $1728$ pairing-based cryptography
Contact author(s)
dimitri koshelev @ gmail com
History
2022-07-02: last of 2 revisions
2021-12-09: received
See all versions
Short URL
https://ia.cr/2021/1604
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1604,
      author = {Dmitrii Koshelev},
      title = {The most efficient indifferentiable hashing to elliptic curves of $j$-invariant $1728$},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1604},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1604}},
      url = {https://eprint.iacr.org/2021/1604}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.