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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.