How can one model a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$?

(Assume $\mathbb{G}_1$ and $\mathbb{G}_2 $ to be additive and multiplicative groups of prime order $q$.)

Normally, for a hash $H: \mathbb{G}_1 \rightarrow \mathbb{G}_1$, we would model it as something like as follows

  • pick $t ∈_R \mathbb{Z}_q$
  • output $tP$ ($P$ is a generator of $\mathbb{G}_1$)
  • $\begingroup$ What do you mean by "model a random oracle hash function"? Also, do you require it to be a group homomorphism? $\endgroup$
    – D.W.
    May 9, 2014 at 5:01
  • $\begingroup$ Usually an "oracle" describes something, that we usually can not do ourselves or an idealized functionality. But about homomorphisms we know quite a lot, so that it doesn't make sense to use an (random) oracle for it. $\endgroup$
    – tylo
    May 9, 2014 at 8:50

1 Answer 1


Assuming that you insist that $H$ preserve the group operation, that is, if $H(A) \times H(B) = H(A+B)$ for any $A, B \in \mathbb{G}_1$, then it would be difficult to come up with an explicit representation (and in any case, the random oracle model doesn't appear to be a great fit).

I'll take the last point first: a random oracle is intended to be something that gives random answers that are consistent with answers that it previously gave. The problem here is that once this Oracle gives one output (e.g. $H(P) = Q$, then (assuming $P \ne 0$), then this determines all other outputs that the random Oracle is allowed to give. Any other input can be represented as $kP$ for some integer $k$ (because all nonidentity elements for a group of prime order are generators), and we insist that $H(kP) = Q^k$.

As for an explicit model of the random Oracle which can be evaluated, well, the problem that runs into is if we select a $\mathbb{G}_1$ where the discrete log problem is hard, and a $\mathbb{G}_2$ where it is easy -- any explicit representation of an Oracle (except for the trivial one $H(P) \equiv 1$) would allow us to solve the discrete log problem in $\mathbb{G}_1$; which we assumed was difficult.

If you don't care whether the model can be evaluated, then it's easy; have the random oracle pick an arbitrary $P \ne 0 \in \mathbb{G}_1$ and a random $Q \in \mathbb{G}_2$; then, whenever it gets a query for $H(kP)$, it just returns $Q^k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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