Paper 2021/678

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.