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 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.

Note: Removed \textit{} from the abstract.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
pairing-based cryptographypairing-friendly elliptic curvesfast hashing
Contact author(s)
budroni alessandro @ gmail com
History
2017-09-06: revised
2017-05-21: received
See all versions
Short URL
https://ia.cr/2017/419
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.