Paper 2021/1604
The most efficient indifferentiable hashing to elliptic curves of $j$-invariant $1728$
Dmitrii Koshelev
Abstract
This article contains a new hash function (indifferentiable from a random oracle) to any ordinary elliptic curve $E_a\!: y^2 = x^3 + ax$ (of invariant $1728$) over a finite field $\mathbb{F}_{\!q}$. Its advantage consists in the necessity to compute (in constant time) only one exponentiation in $\mathbb{F}_{\!q}$, at least for the most practical case $q \equiv 5 \ (\mathrm{mod} \ 8)$. In comparison, for such a $q$ the previous fastest constant-time indifferentiable hash functions to $E_a$ require to compute two exponentiations in $\mathbb{F}_{\!q}$. By the way, the famous Shallue--van de Woestijne hash function (acting as a random oracle) performs four exponentiations in $\mathbb{F}_{\!q}$ even when it is implemented as efficiently as possible. 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 result of the given article seems to be unimprovable.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- Calabi--Yau threefoldsdouble-odd elliptic curveselliptic fibrationsindifferentiable hashing to elliptic curves$j$-invariant $1728$pairing-based cryptographyquartic residue symbol and quartic rootsrational surfacesWeil--Aubry--Perret inequality
- Contact author(s)
- dimitri koshelev @ gmail com
- History
- 2022-12-01: last of 3 revisions
- 2021-12-09: received
- See all versions
- Short URL
- https://ia.cr/2021/1604
- License
-
CC BY