7
$\begingroup$

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: https://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples

Improve this question
$\endgroup$
4
  • $\begingroup$ 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}$... $\endgroup$
    – ratchet freak
    Sep 17, 2011 at 12:17
  • 1
    $\begingroup$ Yes, the question is essentially "are there ways to know $g^{ab}$ without knowing $a$ or $b$?" $\endgroup$
    – Michael Cohen
    Sep 17, 2011 at 22:30
  • $\begingroup$ 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) $\endgroup$
    – ratchet freak
    Sep 17, 2011 at 22:34
  • $\begingroup$ 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. $\endgroup$
    – Michael Cohen
    Sep 18, 2011 at 2:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Michael Cohen
    Sep 26, 2011 at 0:15

Your Answer

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

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