Fast hashing to \(\mathbb{G}_2\) on pairing-friendly curves with the lack of twists (Q6136710)

In pairing based cryptography there are several features required for security and efficiency. Exponentiation and bilinear maps calculations should be efficient and hardness of involved discrete logarithm problems should be maintained. Generally, bilinear maps are of the form \(e:G_1\times G_2\to G_T\) where \(G_1=E(\mathbb{F}_p)[r]\), \(G_2=E[r]\cap\mbox{ker}(\pi-[p])\), \(G_T<\mathbb{F}_{p^k}^*\) is a cyclic group of order \(r\), \(\pi:(x,y)\mapsto(x^p,y^p)\) is the \(p\)-th power Frobenius endomorphism, \(E:y^2=x^3 + ax +b\) is an elliptic curve, \(r\) is a large prime, \(r|o(E(\mathbb{F}_p))\) but \(r^2\not|o(E(\mathbb{F}_p))\), \(p\) is a large prime and \(k\) is the embedding degree of \(E\) with respect to \(r\) i.e. the minimum exponent \(k\) such that \(r|(p^k-1)\). An important action is hashing: given a string of bits a point in a group should be associated to the string. Hashing in \(G_1\) is quite direct: a point in \(E(\mathbb{F}_p)\) is chosen and then it is multiplied by the cofactor \(\frac{1}{r}o(E(\mathbb{F}_p))\). Hashing into \(G_2\) is rather complex. Let \(d=\gcd(k,o(\mbox{Aut}(E)))\). If \(d>0\) then a \(d\)-twist \(E^{(d)}\) exists and \(G_2\) is isomorphic to \(E^{(d)}\left(\mathbb{F}_{p^{\frac{k}{d}}}\right)[r]\) and hashing can be done similarly, although the complexity depends on \(\frac{k}{d}\). If \(d=1\) the case of curves with the lack of twists appears. In this paper firstly several conditions are given to represent \(G_2\) as a cyclic subgroup of the trace zero subgroup of \(E(\mathbb{F}_{p^k})\) and from here a hashing map result although not necessarily efficient. A second procedure is obtained using an alternative represention of \(G_2\) using the cyclotomic zero subgroup of elliptic curves. This construction is very efficient. Thereafter this last procedure is applied within the pairing-friendly curves BW13-P310 and BW19-P286. The authors describe the full implementation of these cases. For sure it is a great contribution for hashing in the use of pairing based cryptography.