4
$\begingroup$

Let $G$ be a cyclic multiplicative group of order $n$. Let $g$ be a (public) generator of $G$. The Diffie-Hellman (DH) problem asks: Given $g^x, g^y\in G$ for $x, y\in \mathbb{Z}^*_n$, to compute $g^{xy}\in G$.

Let $O$ be an oracle that works as follows: it takes as input $g^x\in G$ for any $x \in \mathbb{Z}^*_n$, it outputs $g^{1/x}\in G$. In other words, $O(g^x)=g^{1/x}$. I call this the "Discrete log inversion" oracle for lack of a better name.

Can we use $O$ to solve the DH problem. I remember reading about this somewhere but can't locate the reference.

Note: $1/x$ is defined as the inverse of $x \in\mathbb{Z}^*_n$.

EDIT: To visualize such a group, let $n=15$ and consider the subgroup of $\mathbb{Z}_{31}^*$ generated by 7, which is $\{1, 7, 18, 2, 14, 5, 4, 28, 10, 8, 25, 20, 16, 19, 9\}$, containing exactly 15 elements. In this case $G=\{7^i \bmod{31}|i \in \mathbb{Z}_{15}\}$

$\endgroup$
4
  • $\begingroup$ you want $(O(g^x))^x\equiv g\equiv (g^{1/x})^x \pmod n$ to hold. Right? $\endgroup$
    – SEJPM
    Jun 12, 2015 at 17:45
  • $\begingroup$ if so, I think "$1/x$ is defined as the inverse of $x\in\mathbb{Z}^*_{\phi(n)}$", with $\phi(n)$ denoting the group order. $\endgroup$
    – SEJPM
    Jun 12, 2015 at 18:02
  • $\begingroup$ That's what I meant, if you want that $g^{(1/x)*x}\equiv g \pmod n$, you need to choose $d:=1/x$ such that $e*d\equiv 1 \pmod{\phi(n)}$ (logic stolen from RSA) $\endgroup$
    – SEJPM
    Jun 12, 2015 at 18:28
  • $\begingroup$ @SOJPM; $(O(g^x))^x = g\in G$ (not $\bmod{n}$). Edited question to make this clear. $\endgroup$
    – Jus12
    Jun 12, 2015 at 18:38

1 Answer 1

6
$\begingroup$

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$.

To compute $g^{a^2}$ from $g^a$ using $O$, we perform:

$$ \begin{align} x &= O(g g^a) = g^{1/(1+a) \bmod n} \\ y &= O(g / g^a) = g^{1/(1-a) \bmod n} \\ z &= O((xy)^{1/2 \bmod n}) = g^{1 - a^2} \\ w &= g / z = g^{a^2}. \end{align} $$

Let's call the above procedure $S(\cdot)$. Now, we use the quarter-squares identity

$$ (x + y)^2 - (x - y)^2 = 4xy, $$

to compute $S(g^{a}g^{b}) / S(g^{a}/g^{b}) = S(g^{a+b}) / S(g^{a - b}) = g^{(a+b)^2 - (a-b)^2} = g^{4ab}$. Exponentiate to ${1/4 \bmod n}$ and obtain $g^{ab}$.

$\endgroup$
1
  • $\begingroup$ Thanks for the ref. Some related questions: Suppose $n$ is composite and hard to factor. Which of the problems in Ch 21 are reducible? (1) Can Inverse-DH be reduced to Fixed-Inverse-DH? (2) Can Fixed-Inverse-DH be reduced to Fixed-DH? $\endgroup$
    – Jus12
    Jun 13, 2015 at 6:00

Your Answer

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

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