5
$\begingroup$

From here they define the $\ell$-Diffie Hellman inversion problem as:

Given $g^{a},g^{a^2}\ldots,g^{a^{\ell}} \in G$, compute $g^{a^{-1}}$

Would this problem become easy if the generator $g$ is also known?

$\endgroup$

3 Answers 3

4
$\begingroup$

No.

The stated $l$-DHI problem is believed to remain hard when $g$ is known.

Actually, in the quoted page, it is assumed that $g$ is known throughout. This is obvious in particular in the sections on DLP and CDH.

$\endgroup$
2
  • $\begingroup$ I missed that bit at the top of the page. I got confused because some of the other assumptions list g to be explicitly known. $\endgroup$
    – blz
    Mar 1, 2012 at 6:04
  • $\begingroup$ @blz: You did not miss that bit - it was missing, I added it. $\endgroup$
    – fgrieu
    Mar 1, 2012 at 9:08
3
$\begingroup$

No. The generator $g$ is a public parameter of the group $G$. You cannot perform a Diffie-Hellman handshake unless both parties agree on the generator (as well as any other parameter that defines $G$), so naturally any variation of the Diffie-Hellman problem must, by definition, assume the same thing.

$\endgroup$
3
$\begingroup$

Do you know about the paper Variations of Diffie-Hellman Problem (PDF)? The problem you stated is the generalization of the inversion problem stated in that paper. You can use their technique to prove the relation.

$\endgroup$
1
  • $\begingroup$ I fail to locate the paper. $\endgroup$
    – fgrieu
    Feb 29, 2012 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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