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 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 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>