**Faster indifferentiable hashing to elliptic $\mathbb{F}_{\!q^2}$-curves**

*Dmitrii Koshelev*

**Abstract: **Let $\mathbb{F}_{\!q}$ be a finite field and $E\!: y^2 = x^3 + ax + b$ be an elliptic $\mathbb{F}_{\!q^2}$-curve of $j(E) \not\in \mathbb{F}_{\!q}$. This article provides a new constant-time hash function $\mathcal{H}\!: \{0,1\}^* \to E(\mathbb{F}_{\!q^2})$ indifferentiable from a random oracle. Furthermore, $\mathcal{H}$ can be computed with the cost of $3$ exponentiations in $\mathbb{F}_{\!q}$. In comparison, the actively used (indifferentiable constant-time) simplified SWU hash function to $E(\mathbb{F}_{\!q^2})$ computes $2$ exponentiations in $\mathbb{F}_{\!q^2}$, i.e., it costs $4$ ones in $\mathbb{F}_{\!q}$. In pairing-based cryptography one often uses the hashing to elliptic $\mathbb{F}_{\!q^2}$-curves $E_b\!: y^2 = x^3 + b$ (of $j$-invariant $0$) having an $\mathbb{F}_{\!q^2}$-isogeny $\tau\!: E \to E_b$ of small degree. Therefore the composition $\tau \circ \mathcal{H}\!: \{0,1\}^* \to \tau\big( E(\mathbb{F}_{\!q^2}) \big)$ is also an indifferentiable constant-time hash function.

**Category / Keywords: **implementation / constant-time implementation, hashing to elliptic and hyperelliptic curves, indifferentiability from a random oracle, isogenies, pairing-based cryptography, Weil restriction

**Date: **received 24 May 2021, last revised 8 Jun 2021

**Contact author: **dishport at ya ru

**Available format(s): **PDF | BibTeX Citation

**Version: **20210608:190945 (All versions of this report)

**Short URL: **ia.cr/2021/678

[ Cryptology ePrint archive ]