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.

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$)
share|improve this question
    
What do you mean by "model a random oracle hash function"? Also, do you require it to be a group homomorphism? –  D.W. May 9 at 5:01
    
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. –  tylo May 9 at 8:50

1 Answer 1

up vote 2 down vote accepted

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

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.