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)\notin {\mathbb{F}}_q$. This article provides a new constant-time hash function $\mathcal{H}:\{0,1{\}}^{\ast }\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{\}}^{\ast }\to \tau (E({\mathbb{F}}_{q^2}))$ is also an indifferentiable constant-time hash function.