Paper 2020/1070
Efficient indifferentiable hashing to elliptic curves $y^2 = x^3 + b$ provided that $b$ is a quadratic residue
Dmitrii Koshelev
Abstract
Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary elliptic $\mathbb{F}_{\!q}$curve of $j$invariant $0$ such that $\sqrt{b} \in \mathbb{F}_{\!q}$. In particular, this condition is fulfilled for the curve BLS12381 and for one of sextic twists of the curve BW6761 (in both cases $b=4$). These curves are very popular in pairingbased cryptography. The article provides an efficient constanttime encoding $h\!: \mathbb{F}_{\!q} \to E_b(\mathbb{F}_{\!q})$ of an absolutely new type for which $q/6 \leqslant \#\mathrm{Im}(h)$. We prove that at least for $q \equiv 4 \ (\mathrm{mod} \ 9)$ the hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ induced by $h$ is indifferentiable from a random oracle. The main idea of our encoding consists in extracting in $\mathbb{F}_{\!q}$ (for $q \equiv 1 \ (\mathrm{mod} \ 3)$) a cubic root instead of a square root as in the well known (universal) SWU encoding and in its simplified analogue. Besides, the new hashing can be implemented without quadratic and cubic residuosity tests (as well as without inversions) in $\mathbb{F}_{\!q}$. Thus in addition to the protection against timing attacks, $H$ is much more efficient than the SWU hash function, which generally requires to perform $4$ quadratic residuosity tests in $\mathbb{F}_{\!q}$. For instance, in the case of BW6761 this allows to avoid approximately $4 \!\cdot\! 761 \approx 3000$ field multiplications.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint.
 Keywords
 cubic residue symbol and cubic rootselliptic surfaceshashing to elliptic curvesindifferentiability from a random oraclepairingbased cryptography
 Contact author(s)
 dishport @ ya ru
 History
 20210618: last of 7 revisions
 20200909: received
 See all versions
 Short URL
 https://ia.cr/2020/1070
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1070, author = {Dmitrii Koshelev}, title = {Efficient indifferentiable hashing to elliptic curves $y^2 = x^3 + b$ provided that $b$ is a quadratic residue}, howpublished = {Cryptology ePrint Archive, Paper 2020/1070}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1070}}, url = {https://eprint.iacr.org/2020/1070} }