[Resource Topic] 2017/419: Efficient hash maps to \mathbb{G}_2 on BLS curves

Welcome to the resource topic for 2017/419

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

Authors: Alessandro Budroni, Federico Pintore


When a pairing e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \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=\#\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 k=42,48, 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.

ePrint: https://eprint.iacr.org/2017/419

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .