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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2021/1604

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.