# Discrete Logarithm problem with inverse

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.

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

## 2 Answers

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.

• 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. Commented Oct 20, 2015 at 12:51
• However, it does seem analogous to the Strong-DDH problem but transposed to the Discrete Logarithm. Maybe something like the "Strong Discrete Logarithm problem"... Commented Oct 20, 2015 at 12:53
• Bingo. I withdraw the (-1) as a thank you for the inspiration :) Commented Oct 20, 2015 at 12:58
• Apply logical contraposition to the implication in your comment and you get the resukt that your problem is not solveable.
– user27950
Commented Oct 20, 2015 at 13:00