How can we determine if two discrete logarithms are equal?

Question

Let $p$ be a prime number, and let $g_{1},g_{2},...,g_{n}$ be $n$ generator of $Z^{*}_{p}$. We have a list $y_{1},y_{2},\dotsc,y_{n}$ of elements in $Z^{*}_{p}$ such that for every $i\in \lbrace1,2,\dotsc,n \rbrace$ we have $y_{i}=g_{i}^{x_{i}} \bmod p$ for some number $x_{i}$ (but we don't know $x_{i}$). I am trying to find an algorithm to determine all pairs $(y_{i},y_{j})$, $i\neq j$ such that $x_{i}=x_{j}$.

Answer 1

This problem is equivalent to the decisional Diffie-Hellman problem, and hence your problem is intractable (assuming, of course, that the group is well chosen).

Here's how we can use an Oracle that can solve the above problem to solve the DDH problem:

• In the DDH problem, we're given values $g, g^x, g^y, g^z$, and we're asked whether $xy = z$.

• We call the Oracle with the following instance: $n=2$, $g_1 = g$, $g_2 = g^x$, $y_1 = g^y$, $y_2 = g^z$.

• The Oracle will return that $x_1 = x_2$ is a matching pair iff, for that same $w$, $g_1^w = y_1$ and $g_2^w = y_2$, that is, if $g^w = g^y$ and $g^{wx} = g^z$, which is to say, if $g^{xy} = g^z$

It's also obvious how to solve your problem with an Oracle that solves the DDH problem (using $n (n-1)/2$ calls to the Oracle).