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

In pairing based cryptography, bilinear maps \(e:\mathbb{G}_1\times\mathbb{G}_2\to\mathbb{G}_T\) are considered where \(\mathbb{G}_1,\mathbb{G}_2\) are groups of a given order \(r\). In applications it is very important to hash binary strings into each of these subgroups. For a given elliptic curve, say \(E(\mathbb{F}_{p^m})\), if \(r|o(E(\mathbb{F}_{p^m})\) but \(r^2\not|o(E(\mathbb{F}_{p^m})\) then there is just one subgroup of order \(r\) within \(E(\mathbb{F}_{p^m})\). Let \(\mathbb{G}_1<E(\mathbb{F}_{p^m})\) be such subgroup. In order to hash into \(\mathbb{G}_1\) it is sufficient to hash into a point \(\mathbf{x}\in E(\mathbb{F}_{p^m})\) and then to calculate \(\mathbf{y} = c\mathbf{x}\) for the cofactor \(c=\frac{1}{r}o(E(\mathbb{F}_{p^m})\). Usually, \(\mathbb{G}_2\) is taken as \(\tilde{E}(\mathbb{F}_{p^{\frac{m}{d}}})\cap\tilde{E}[r]\) where \(\tilde{E}\) is a twist of \(E\) of degree \(d\) with \(d|m\). In this last case it is important to realize the product of points \(\tilde{E}(\mathbb{F}_{p^{\frac{m}{d}}})\) by the cofactor \(c\) in an efficient way. The authors consider the methods exposed in [\textit{M. Scott} et al., Lect. Notes Comput. Sci. 5671, 102--113 (2009; Zbl 1248.94094)] and [\textit{L. Fuentes-Castañeda} et al., Lect. Notes Comput. Sci. 7118, 412--430 (2012; Zbl 1292.94063)] applied to the family of BLS-curves, defined by Barreto, Lynn and Scott, for \(d=6\) and \(k\in\{12, 24, 30, 42, 48\}\). They verifed that for \(k\in\{12, 24, 30\}\) the method in [\textit{L. Fuentes-Castañeda} et al., Lect. Notes Comput. Sci. 7118, 412--430 (2012; Zbl 1292.94063)] is more efficient than the methods in [\textit{M. Scott} et al., Lect. Notes Comput. Sci. 5671, 102--113 (2009; Zbl 1248.94094)] but for \(k\in\{42, 48\}\) the method in [\textit{L. Fuentes-Castañeda} et al., Lect. Notes Comput. Sci. 7118, 412--430 (2012; Zbl 1292.94063)] is rather expensive, hence the authors derive a variation of this last method in order to provide an efficient method for \(k\in\{42, 48\}\).