[Resource Topic] 2020/1070: Efficient indifferentiable hashing to elliptic curves $y^2 = x^3 + b$ provided that $b$ is a quadratic residue

Welcome to the resource topic for 2020/1070

Title:
Efficient indifferentiable hashing to elliptic curves y^2 = x^3 + b provided that b is a quadratic residue

Authors: 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 BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases b=4). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time 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 BW6-761 this allows to avoid approximately 4 \!\cdot\! 761 \approx 3000 field multiplications.

ePrint: https://eprint.iacr.org/2020/1070

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .