1
$\begingroup$

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

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

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).
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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