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 \rightarrow \mathbb{G}_{T}$, on an elliptic curve $E$ defined over $\mathbb{F}_q$, is exploited for an identitybased 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 pairingfriendly curves having $k \in \{12,24,30,42,48\}$, providing efficiency comparisons. When $k=42,48$, the Fuentes et al. method requires an expensive oneoff precomputation 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.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 pairingbased cryptographypairingfriendly elliptic curvesfast hashing
 Contact author(s)
 budroni alessandro @ gmail com
 History
 20170906: revised
 20170521: received
 See all versions
 Short URL
 https://ia.cr/2017/419
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/419, author = {Alessandro Budroni and Federico Pintore}, title = {Efficient hash maps to \mathbb{G}_2 on BLS curves}, howpublished = {Cryptology ePrint Archive, Paper 2017/419}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/419}}, url = {https://eprint.iacr.org/2017/419} }