Paper 2021/301

Indifferentiable hashing to ordinary elliptic ${\mathbb{F}}_q$-curves of $j=0$ with the cost of one exponentiation in ${\mathbb{F}}_q$

Dmitrii Koshelev

Abstract

Let ${\mathbb{F}}_q$ be a finite field and $E_b:y^2=x^3+b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b}\in {\mathbb{F}}_q$ and $q\not\equiv 1(\mathrm{mod}27)$. For example, these conditions are fulfilled for the curve BLS12-381 ($b=4$). It is a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H:\{0,1{\}}^{\ast }\to E_b({\mathbb{F}}_q)$ indifferentiable from a random oracle. Its main advantage is the fact that $H$ computes only one exponentiation in ${\mathbb{F}}_q$. In comparison, the previous fastest constant-time indifferentiable hash functions to $E_b({\mathbb{F}}_q)$ compute two exponentiations in ${\mathbb{F}}_q$. In particular, applying $H$ to the widely used BLS multi-signature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.