<p>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.</p>

CC BY-SA 3.0
2011-09-26T00:15:36.620Z
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
CC BY-SA 3.0
2011-09-25T06:39:23.283Z
2011-09-25T06:39:23.283Z
Clint Givens
<p>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?</p>

<p>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)$?</p>

<p>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).</p>

<p>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.</p>

<p>Now cross-posted on mathoverflow: <a href="https://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples">https://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples</a></p>

CC BY-SA 3.0
2011-09-17T12:17:59.927Z
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
CC BY-SA 3.0
2011-09-17T22:30:10.040Z
Yes, the question is essentially "are there ways to know $g^{ab}$ _without_ knowing $a$ or $b$?"
Michael Cohen
CC BY-SA 3.0
2011-09-17T22:34:05.227Z
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
CC BY-SA 3.0
2011-09-18T02:04:26.573Z
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
<cr.crypto-security><nt.number-theory>
Generating a Diffie Hellman tuple without "being able to know" one of the discrete logs involved
Michael Cohen
# Generating a Diffie Hellman tuple without "being able to know" one of the discrete logs involved

(Asked by: username_0 on 2011-09-16)

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>

**Tags:** cr.crypto-security, nt.number-theory
> **Comments:**
> **username_1**: 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}$...  
> **username_0**: Yes, the question is essentially "are there ways to know $g^{ab}$ _without_ knowing $a$ or $b$?"  
> **username_1**: 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)  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-09-25. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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!  

---

