2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Maeher
    May 15 at 9:49
  • $\begingroup$ OK, but how does that help the attacker in finding $y$ (or am I misreading your argument) EDIT: Oh, I got it, thanks. $\endgroup$
    – crypcrypcryp
    May 15 at 10:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Maeher
    May 15 at 10:17

1 Answer 1

Reset to default
5
$\begingroup$

This is equivalent to the discrete logarithm problem.

Clearly if I can solve the discrete logarithm problem, I can solve your problem.

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

Thus if I can solve your problem, I can solve the discrete logarithm problem for the group.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This assumes that the attacker can select $h$. $\endgroup$
    – crypcrypcryp
    May 15 at 10:19
  • 3
    $\begingroup$ No, the randomisation of $r$ gives a random instance of your problem conditioned on one of the generators being $g$. $\endgroup$
    – Daniel S
    May 15 at 10:26

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.