Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$.

share|improve this question
3  
I guess they mean "treat the hash function to $G_2$ as a random oracle", because $H(m)=h(m)Q$ is problematic as you know the discrete log with respect to $Q$. Consider for instance the BLS signature with such a type of hash function. Then the scheme is completely broken. –  DrLecter Oct 28 '13 at 17:55
1  
Btw: In your question you write: "In this type of pairing we have a group homomorphism from G2 to G1." Note that since the groups are of the same order they are always isomorphic. However, in case of Type-2 pairings an efficient computable isomorphism between $G_2$ and $G_1$ is known, whereas in Type-3 pairings such an efficient computable isomorphism is conjectured not to exist. –  DrLecter Oct 29 '13 at 6:26

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.