2
$\begingroup$

Let $\mathbb G$ be a cyclic group of order $q$. The Discrete Logarithm Problem (DLP) is, given $g, g^x \in \mathbb G$, to compute $x \in \mathbb Z_q $.

I'm interested to know if there is a known variant of DLP as follows:

Given $g, g^x, g^{x^{-1}\bmod q} \in \mathbb G$, compute $x \in \mathbb Z_q$

It is clear that this variant would not be harder than the DLP, since a DLP solver could be used to solve this problem simply by ignoring the third input.

$\endgroup$
  • $\begingroup$ try to find a copy of this report: ICT-2007-216676 ECRYPT II European Network of Excellence in Cryptology II. They collect many computational hypothesis and gave all the definitions. (a link to the final version: cordis.europa.eu/docs/projects/cnect/6/216676/080/deliverables/…) $\endgroup$ – ddddavidee Oct 20 '15 at 9:59
  • $\begingroup$ @ddddavidee I'm familiar with that report and I'm afraid the answer is not there :( $\endgroup$ – cygnusv Oct 20 '15 at 10:03
  • $\begingroup$ In what group is $1/x$ computed, or/and how is $g^{1/x}$ defined? How does that differ from $g^{-x}$, which has an accepted definition (and would make it trivial that the problem is equivalent to the DLP) ? $\endgroup$ – fgrieu Oct 20 '15 at 10:41
  • $\begingroup$ @fgrieu Maybe I'm abusing the notation: $1/x$ is actually $x^{-1} \mod q$ $\endgroup$ – cygnusv Oct 20 '15 at 10:43
  • 1
    $\begingroup$ @cygnusv: now that's all clear to me; $1/x$ is modulo $q$, the order of $g$; that's a most natural notation (and ah you made it even clearer; would be a good use case for \bmod rather than \mod, though; and $x \in \mathbb Z_q$ is enough in any case). The difficulty might also depend on if $q$ is a given or not. In either case I know no answer. $\endgroup$ – fgrieu Oct 20 '15 at 10:51
0
$\begingroup$

This is the Strong-DDH: strong decision Diffie-Hellman problem. See Final Report on Main Computational Assumptions in Cryptography. Assumption number 19.

If the DDH is hard then this implies that it must also be hard to calculate the discrete log.

$\endgroup$
  • $\begingroup$ I think this is wrong. The problem I am asking is, ultimately, to compute a discrete logarithm (in other words, a computational problem), while the strong-DDH is a decisional problem. In fact, a solver for the problem I am asking can be used for solving the strong-DDH problem, while the opposite does not seem to be true. PD: Sorry for not commenting before, I got interrupted at work. $\endgroup$ – cygnusv Oct 20 '15 at 12:51
  • $\begingroup$ However, it does seem analogous to the Strong-DDH problem but transposed to the Discrete Logarithm. Maybe something like the "Strong Discrete Logarithm problem"... $\endgroup$ – cygnusv Oct 20 '15 at 12:53
  • $\begingroup$ Bingo. I withdraw the (-1) as a thank you for the inspiration :) $\endgroup$ – cygnusv Oct 20 '15 at 12:58
  • $\begingroup$ Apply logical contraposition to the implication in your comment and you get the resukt that your problem is not solveable. $\endgroup$ – user27950 Oct 20 '15 at 13:00
0
$\begingroup$

This problem seem to be equivalent to a particular instance of the $k$-Strong Discrete Logarithm Problem.

Let $\mathbb G$ be a cyclic group of order $q$. The $k$-Strong Discrete Logarithm Problem ($k$-DLP) is, given $h, h^x, h^{x^2}, .., h^{x^k} \in \mathbb G$, to compute $x \in \mathbb Z_q $. Taking a simple change of variable ($h^x = g$), one obtains an equivalent version of the problem, which is as follows:

Given $g^{x^{-1}\bmod q}, g, g^x, ..., g^{x^{k-1}} \in \mathbb G$, compute $x \in \mathbb Z_q $

It can be seen then that the problem in the question is the case of $k=2$.

The $k$-Strong Discrete Logarithm Problem is discussed in this paper, for instance.

$\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.