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.

  • $\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
    Commented Oct 20, 2015 at 9:59
  • $\begingroup$ @ddddavidee I'm familiar with that report and I'm afraid the answer is not there :( $\endgroup$
    – cygnusv
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 10:41
  • $\begingroup$ @fgrieu Maybe I'm abusing the notation: $1/x$ is actually $x^{-1} \mod q$ $\endgroup$
    – cygnusv
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 10:51

2 Answers 2


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 Correlated-Input Secure Hash Functions by Goyal, O'Neill, and Rao, for instance.


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.

  • $\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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 12:53
  • $\begingroup$ Bingo. I withdraw the (-1) as a thank you for the inspiration :) $\endgroup$
    – cygnusv
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 13:00

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.