# Decisional Discrete Logarithm problem?

Has the decisional version of the discrete logarithm problem been studied somewhere? I mean, for known $$G$$ in a group, distinguishing $$xG$$ and $$Y$$ for unknown integer $$x$$ and group element $$Y$$?

• but there's also some $y$ s.t. $yG=Y$ so how would you distinguish $yG$ from $xG$? Mar 5, 2020 at 11:24

The standard discrete logarithm assumption asks, given a group $$\mathbb{G}$$ of order $$p$$ with generator $$G$$, to compute $$x$$ given $$xG$$, where $$x$$ is a random. This means that $$\{xG : x \gets \mathbb{Z}_p\}$$ spans the entire group, so $$xG$$ is exactly a uniformly random group element. You cannot possibly hope to distinguish it from random, since it's perfectly distributed as a random group element.
• distinguish $$xG$$ for a random even $$x \gets \mathbb{Z}_p$$ and $$xG$$ for a random odd $$x \gets \mathbb{Z}_p$$ (even and odd are defined by viewing $$x$$ as an integer between $$0$$ and $$p-1$$). This decision problem is equivalent to the computational discrete logarithm (the proof is a standard exercise, at least when the success probability is assumed to be 1 - it's harder in the general case).
• distinguish $$xG$$ from a random group element, when $$x$$ is a random short element (e.g. between $$0$$ and $$2^k$$ for some $$k$$ related to the security parameter, such that $$2^k$$ is much smaller than $$p$$). This problem actually reduces to the computational "short-exponent discrete logarithm assumption", which asks to find $$x$$ given $$xG$$ for a random short $$x$$ (proof here).