Decisional Discrete Logarithm problem?

Question

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

Answer 1

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.

That being said, there are "decisional variants" of the discrete logarithm problem:

• 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).