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., nonsupersingular) 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 BLS12381 ($b=4$). It is a de facto standard in the real world pairingbased cryptography at the moment. This article provides a new constanttime 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 constanttime 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 multisignature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint.
 Keywords
 cubic residue symbol and cubic rootsindifferentiability from a random oraclepairingbased cryptography
 Contact author(s)
 dimitri koshelev @ gmail com
 History
 20210929: last of 7 revisions
 20210309: 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}, note = {\url{https://eprint.iacr.org/2021/301}}, url = {https://eprint.iacr.org/2021/301} }