Paper 2017/419

Efficient hash maps to \mathbb{G}_2 on BLS curves

Alessandro Budroni and Federico Pintore

Abstract

When a pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$, on an elliptic curve $E$ defined over ${\mathbb{F}}_q$, is exploited for an identity-based protocol, there is often the need to hash binary strings into ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$. Traditionally, if $E$ admits a twist $\tilde{E}$ of order $d$, then ${\mathbb{G}}_1=E({\mathbb{F}}_q)\cap E[r]$, where $r$ is a prime integer, and ${\mathbb{G}}_2=\tilde{E}({\mathbb{F}}_{q^{k/d}})\cap \tilde{E}[r]$, where $k$ is the embedding degree of $E$ w.r.t. $r$. The standard approach for hashing into ${\mathbb{G}}_2$ is to map to a general point $P\in \tilde{E}({\mathbb{F}}_{q^{k/d}})$ and then multiply it by the cofactor $c=\mathrm{\#}\tilde{E}({\mathbb{F}}_{q^{k/d}})/r$. Usually, the multiplication by $c$ is computationally expensive. In order to speed up such a computation, two different methods (by Scott et al. and by Fuentes et al.) have been proposed. In this paper we consider these two methods for BLS pairing-friendly curves having $k\in \{12,24,30,42,48\}$, providing efficiency comparisons. When $$, the Fuentes et al. method requires an expensive one-off pre-computation which was infeasible for the computational power at our disposal. In these cases, we theoretically obtain hashing maps that follow Fuentes et al. idea.

Note: Removed \textit{} from the abstract.