Mapping to G1/G2

[arybczak]

I've looked at the "Indifferentiable hashing to Barreto Naehrig curves" paper and for Fp254BNb the assumption that g(1) = 1 + b is a nonzero quare in Fp does not hold, which I assume is the reason why mapping fails for sqrt(-3) and -sqrt(-3). I didn't study these proofs closely to see whether the broken assumption leads to other values that will not be mappable. Do you know of any? Also, what about G2?

As a side note, page 3 of the paper has an interesting remark:

like Icart’s encoding and many others, this encoding f will not yield a gener-
ically secure hash function construction if we simply compose it with a ran-
dom oracle to the base field (e.g. it is easy to distinguish such a hash function
from a random oracle to the curve since its image has a simple algebraic de-
scription and only contains a constant fraction of all points). However, we
show (in Section 5) that it is well-distributed in the sense of Farashahi et al.
[17]. This implies
 that if h1 , h2 are random oracles to the base field, then
m -> f(h1(m)) + f(h2(m)) is a good, generically secure hash function to the
BN curve (it is indifferentiable from a random oracle);

However, it seems this is what BN256_G1_hashAndMapTo (and G2 variant) do, i.e. they just hash a message to a value in Fp and then map this value to get a point on the curve.

[arybczak]

Presumably the latter issue can be solved by hashing a message with SHA512, then mapping upper half to one point, lower half to another (although it seems like truncation of SHA-2 hashes is fine if you take leftmost bits, I didn't find anything about rightmost bits, so it might not be a good approach) mapping both to a curve point and adding them.

[herumi]

whether the broken assumption leads to other values that will not be mappable.

Algorithm 1 Step 2 in page 15 of the paper, the denominator 1 + b + t^2 is equal to 0 if t = sqrt(-3) or -sqrt(-3).

[herumi]

I don't know detail of security of map function. I'll read Indifferentiable Deterministic Hashing to Elliptic and Hyperelliptic Curves. But if f(h1(m)) + f(h2(m)) is necessary for some application, it is easy to make it with MapToT<Fp> in the software.