3
$\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$
  • $\begingroup$ you want $(O(g^x))^x\equiv g\equiv (g^{1/x})^x \pmod n$ to hold. Right? $\endgroup$ – SEJPM Jun 12 '15 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 '15 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 '15 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 '15 at 18:38
5
$\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$
  • $\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 '15 at 6:00

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.