Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without "being able to know" one of the discrete logs involved (formal definition given in question)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T16:06:17Z http://mathoverflow.net/feeds/question/76302 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without "being able to know" one of the discrete logs involved (formal definition given in question)? Michael Cohen 2011-09-24T23:58:21Z 2011-10-10T00:22:12Z <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 particularly 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>Cross-post from CSTheory stackexchange: <a href="http://cstheory.stackexchange.com/questions/8245/generating-a-diffie-hellman-tuple-without-being-able-to-know-one-of-the-discret" rel="nofollow">http://cstheory.stackexchange.com/questions/8245/generating-a-diffie-hellman-tuple-without-being-able-to-know-one-of-the-discret</a></p> http://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples/76373#76373 Answer by Michael Cohen for Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without "being able to know" one of the discrete logs involved (formal definition given in question)? Michael Cohen 2011-09-26T00:17:50Z 2011-09-26T00:17:50Z <p>Clint Givens on the cstheory stackexchange pointed out that this is essentially the KEA-DH "Knowledge of Exponent" assumption used in "Statistically Hiding Sets" by Prabhakaran and Xue.</p>