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.

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?

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  blz Mar 1 '12 at 6:04
    
@blz: You did not miss that bit - it was missing, I added it. –  fgrieu Mar 1 '12 at 9:08
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
I fail to locate the paper. –  fgrieu Feb 29 '12 at 16:30
1  
Thanks for pointing. I corrected the link. –  Jalaj Feb 29 '12 at 16:43
    
the link is now perfect, thanks. –  fgrieu Mar 1 '12 at 9:08
add comment

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.