Description
(This issue has been imported from the Gitlab repository because it seems to not have been addressed yet)
Original Text (Issue 199)
Comment by Jan Bobolz
... if feasible. I currently wouldn't know how. [at]peterg any insights?
I guess in the random oracle model you might just hash to a random polynomial and then exponentiate with the cofactor?
Comment by Peter Günther
Actually, I think there should be a more efficient method for Type 1 and Type 3 pairings. The keyword is Torus based cryptography and pairing compression (see Chapter 3 of Naehrigs Phd Thesis or chapter 6.2 of the Galbraith book und mathematics of public key cryptography).
The method proposed by Jan does not work in general, although I forgot what the real problem was. I remember a paper that said that hashing to Gt is only securely possible for supersingular pairings. I cannot find the paper now and I forgot a lot of things.
One thing that you need to consider is that your collision resistant hash function into the extension field has to cover the complete extension field. If you hit only subfields, the combination with cofactor exp. will not be collision resistant because cofactor exponentiation maps all elements of a proper subfield to 1. (Gt is a subgroup of the Norm 1 subgroup, The Norm 1 subgroup is in the kernel of cofactor exponentiation).
For the supersingular case there is also a more efficient way. Look at Definition 6.3.7 of the Galbraith book.
Let Fq^2 = Fq(a) and a' the conjugate of a (a'=a^q). Then f(x)=(x+a)/(x+a') should be a bijective mapping from Fq to Gt. For the theory, look at the book. The point is that you get an element with norm 1. The norm 1 subgroup contains Gt. Hence, basically one inversion. (Actually, efficient impl. of cofactor exp. also fall back to the inversion trick with the conjugate).
Maybe the following work also helps to judge security. It is about G1 and G2, but still it might help to understand security implications. I did not check it again.
Indifferentiable Hashing
to Barreto–Naehrig Curves
Pierre-Alain Fouque1 and Mehdi Tibouchi2
Efficient Indifferentiable Hashing into Ordinary
Elliptic Curves
Eric Brier1, Jean-S´ebastien Coron2, Thomas Icart2,�, David Madore3,
Hugues Randriam3, and Mehdi Tibouchi2,4