# Security of equal discrete logs (over different bases)

I am trying to find a reduction for the following DLOG problem in generic groups. It is a simple generalization but I'm not finding any reference (the closest being the Chaum-Pedersen signature scheme sec 3.2, and BLS signatures without the hashing).

Let $$G$$ be a cyclic group, and $$g, h$$ generators. The problem is to find $$y$$ given $$g^y, h^y$$.

Looking for any insight or reference.

• Given $g$ and challenge Choose random $r$ such that $g^r$ is a generator. (Easy in prime order groups.) Set $h:=g^r$ and let $h^y := (g^y)^r$. May 15 at 9:49
• OK, but how does that help the attacker in finding $y$ (or am I misreading your argument) EDIT: Oh, I got it, thanks. May 15 at 10:13
• It doesn't. That's the point. It's a short description of the reduction from dlog to your problem. This reduction (described in more detail in Daniel S' answer below) shows that your problem is no easier than dlog. May 15 at 10:17

Given an instance of the discrete logarithm problem e.g. given $$x=g^y$$ find $$y$$, I can generate an instance of your problem by choosing a random $$r$$ coprime to the group order and setting $$h=g^r$$. In this case I can also compute $$x^r$$ which will be $$h^r$$.
• This assumes that the attacker can select $h$. May 15 at 10:19
• No, the randomisation of $r$ gives a random instance of your problem conditioned on one of the generators being $g$. May 15 at 10:26