Why is a simple hash into $G_2$ for (certain) pairing based crypto not possible?

Question

In the paper Pairings for Cryptographers we read about what the authors call a type 2 pairing in which we have a "pairing friendly curve $E$ over $\mathbb{F}_q$ with embedding degree $k>1$ and define $G_1$ to be the subgroup of $E(\mathbb{F}_q)$ of order $l$". We also define $G_2=\langle Q\rangle$ where $Q\in E(\mathbb{F}_{q^k})[l]$. In this type of pairing we have a group homomorphism from $G_2$ to $G_1$.

The authors go on to say

The advantage of the Type 2 setting is that we can use any curve and still get a homomorphism from $G_2$ to $G_1$. The disadvantage is that the group $G_2$ has no special structure. It seems to be impossible to sample randomly from $G_2$ except by computing multiples of the generator $Q$, hence we cannot securely hash to $G_2$.

Why is computing multiples of the generator $Q$ not a secure way to hash into $G_2$? For instance, say the order of $G_2$ is larger than $2^{256}$. Why couldn't I use a 256 bit hash function $h$ to help hash into $G_2$? Specifically my hash $H:M\to G_2$ where $M$ is the plaintext space would be something like $H(m)=h(m)Q$.

Answer 1

What the authors of the paper cited by you certainly mean by secure is "treat the hash function to $G_2$ as a random oracle". The problem is that hashing to $G_2$ can only be realized by taking some point in the group and multiplying it with a scalar (which is for instance the output of a full domain hash mapping to integers in $Z_{ord(G_2)}^*$). See for instance here for fast methods, which, however, also do not yield "secure" hashing to $G_2$.

It is best explained by an example why such simple hash functions (multiply scalar with some fixed point) can yield to insecure cryptographic protocols. In the example below, I use a type 1 setting for illustration purposes (BLS signatures in type 2 pairings are still secure under a slighly different assumption - co-CDHP instead of CDHP - since one can use a secure hash function $H$ to $G_1$).

The security of BLS essentially relies on treating the hash function $H$ as random oracle, i.e, the output of $H$ cannot be determined unless by querying $H$.

Let us take a look at the BLS setting, where we have $G, G_T$ to be prime order $p$ groups and let $P$ be a generator of $G$ and $e:G\times G\rightarrow G_T$.

Then the private key $x$ is a random element of $Z_p$ and the public key is $X=xP$.

• Signing a message $m$ amounts to computing $S=H(m)$, where $H:\{0,1\}^*\rightarrow G$ is modelled as a random oracle that maps from strings to elements of $G$, and setting the signature as $\sigma=xS$.
• Signature verification when given $m$ and $\sigma$ is to check if $e(H(m),X)=e(\sigma,P)$.

Note that if we would make an extremely bad choice and choose an "insecure" $H$ as $H(m):=H'(m)P$ where $H':\{0,1\}^*\rightarrow Z_p^*$ is a secure hash function, then anybody can forge signatures by computing $\sigma=H'(m)X$ for arbitrary messages (this is essentially the strategy of simulating the random oracle used in the security proof).

So, the signature scheme (and other pairing based protocols that require $H$ to be modeled as a random oracle) live from the fact that the output of $H$ is unpredictable and in particular the discrete log with respect to the generator is not known.

A type of pairings that allow to securely hash into $G_2$ and where there is also an efficiently computable homomorphism from $G_2$ to $G_1$ are so called type 4 pairings.