Paper 2021/301
Indifferentiable hashing to ordinary elliptic $\mathbb{F}_{\!q}$-curves of $j=0$ with the cost of one exponentiation in $\mathbb{F}_{\!q}$
Dmitrii Koshelev
Abstract
Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b} \in \mathbb{F}_{\!q}$ and $q \not\equiv 1 \: (\mathrm{mod} \ 27)$. For example, these conditions are fulfilled for the curve BLS12-381 ($b=4$). It is a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ indifferentiable from a random oracle. Its main advantage is the fact that $H$ computes only one exponentiation in $\mathbb{F}_{\!q}$. In comparison, the previous fastest constant-time indifferentiable hash functions to $E_b(\mathbb{F}_{\!q})$ compute two exponentiations in $\mathbb{F}_{\!q}$. In particular, applying $H$ to the widely used BLS multi-signature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- cubic residue symbol and cubic rootsindifferentiability from a random oraclepairing-based cryptography
- Contact author(s)
- dimitri koshelev @ gmail com
- History
- 2021-09-29: last of 7 revisions
- 2021-03-09: received
- See all versions
- Short URL
- https://ia.cr/2021/301
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/301,
author = {Dmitrii Koshelev},
title = {Indifferentiable hashing to ordinary elliptic $\mathbb{F}_{\!q}$-curves of $j=0$ with the cost of one exponentiation in $\mathbb{F}_{\!q}$},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/301},
year = {2021},
url = {https://eprint.iacr.org/2021/301}
}