Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, and including cases in which Decisional Diffie Hellman is easy) to generate tuples of the form $(g, g^a, g^b, g^{ab})$ without in a sense "knowing" either a or b?

More formally, if there is a polynomial-time Turing machine $T(G, c)$ such that $T$ maps any input into such a tuple in the group described by $G$ ($G$ could just be a modulus if this is a modular multiplicative group, and $c$ could be thought of as random bits), must there exist a polynomial-time $T'$ such that $T'$, with the same input as $T$, outputs $(g, g^a, g^b, g^{ab}, a)$ or $(g, g^a, g^b, g^{ab}, b)$?

Clearly, the answer to this question is not known since there is always such a $T'$ if discrete log is easy and there is is a $T$ without such a $T'$ if Diffie Hellman is easy and discrete log is hard. I'm particular interested in whether there is some existence result that says there must be a $T$ with no such $T'$ (under an assumption like hardness of discrete log), or whether there is a general conjecture that such a $T'$ always exists (or better yet, that this is implied by some other, widely believed, conjecture).

For further context, I'm essentially curious about whether the assumption that such a $T'$ always exists would be considered reasonable in an analysis of a cryptographic protocol.

Now cross-posted on mathoverflow: http://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples

share|improve this question
it boils down t if you know $g^a$ and $b$ you know $g^{ab}$ and if you know $g^b$ and $a$ you know $g^{ba}$ and because $g^{ab}=g^{ba}$... –  ratchet freak Sep 17 '11 at 12:17
Yes, the question is essentially "are there ways to know $g^{ab}$ without knowing $a$ or $b$?" –  Michael Cohen Sep 17 '11 at 22:30
only knowing $g$ $g^a$ and $g^b$, not without calculating the log which is exactly what the exchange relies on (they get transmitted plaintext to be read by the onmipresent MiM) –  ratchet freak Sep 17 '11 at 22:34
Just to be clear, I'm not asking whether Diffie-Hellman is believed to be hard (I know the answer is yes). But that problem is to find $g^{ab}$ given a fixed $g$, $g^a$ and $g^b$. I'm rather asking about the possibility of efficiently generating all four of these at once (actually, I'm also interested in the case where $g$ is fixed but the others can be chosen) with some method that cannot also generate $a$ or $b$. Please see my formal definition, or explain why it is unclear. –  Michael Cohen Sep 18 '11 at 2:04
add comment

1 Answer

up vote 2 down vote accepted

It looks as though the case with a fixed $g$ has shown up under the name "knowledge of exponent assumption(s)"--Googling this phrase will turn up a few papers which discuss/use it. In particular I notice "Statistically Hiding Sets" by Prabhakaran and Xue claims to show the assumption holds in the generic group model. There may be more recent information out there, but that should serve as a starting point at least. Long story short, as far as I can tell: It's a nonstandard assumption, but it's not obviously false and some people have built things with it.

share|improve this answer
It looks like there are multiple variations on this assumption, but the KEA-DH in the "Statistically Hiding Sets" paper looks to be pretty much what I was asking for. Thanks! –  Michael Cohen Sep 26 '11 at 0:15
add comment

Your Answer


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.