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}$.

  • $\begingroup$ If you know what powers of one generator results in the other generators then the problem is easy. Please clarify your question to indicate whether this is the case or not. $\endgroup$ – Barack Obama Jan 11 '13 at 2:06

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).

| improve this answer | |
  • $\begingroup$ I believe there are some groups in which the decisional DH problem is easy, but the computational DH problem is hard. These are useful for some unusual protocols. $\endgroup$ – CodesInChaos Jan 9 '13 at 19:51
  • 1
    $\begingroup$ @CodesInChaos: yes, there are such groups; however, the group $Z^{*}_{p}$ is not one of them. $\endgroup$ – poncho Jan 9 '13 at 19:55
  • $\begingroup$ @poncho: yes i see it on wiki it says that given $g^a$ and $g^b$ one can efficiently compute the Legendre symbol of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element. i wonder how it works? thanks $\endgroup$ – T.B Sep 20 '13 at 13:04
  • $\begingroup$ @Alex: well, if $g$ is a generator for $Z_p^*$, then computing the Legendre symbol on $g^x$ gives you $x \bmod 2$. Hence, given $g^a$, $g^b$, $g^c$, if we see that $ab \ne c \bmod 2$, then we know that $g^{ab} \ne g^c$. This disqualifies half the possible $g^c$ values from being $g^{ab}$. $\endgroup$ – poncho Sep 20 '13 at 13:44
  • $\begingroup$ @poncho: But there are also occasion $ab\equiv c \pmod2$ such that $g^{ab}\neq g^c$ that you cannot distinguish $\endgroup$ – T.B Sep 20 '13 at 14:08

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.