# Can one detect if two pairs of elements in Zp have the same exponential relation?

Suppose that $p$ is a safe prime of 2048 bits ($p = 2q + 1$, and $q$ is prime). Suppose that one is given two pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that:

$y_1 = x_1^{r_1} \pmod p$

$y_2 = x_2^{r_2} \pmod p$

Where $r_1$ and $r_2$ are unknowns.

Is it easy or hard to check if $r_1 = r_2$ without further knowledge? Does this problem have a name?

Is there a relation $f$ of $r$ and $x$, $y_1 = f(r,x_1)$, such that it is difficult to extract $r$ from it but it's easy to detect if the same $r$ is used in another pair $y_2=f(r,x_2)$ without leaking $r$?

• I believe there are some groups which have this property. I think the lucre paper briefly mentioned them. – CodesInChaos Mar 9 '13 at 15:00

This is another way of expressing the decisional Diffie-Hellman problem. This problem is more typically written as 'given $g,\ g^a, g^b, g^c$, does $g^{ab} = g^c$?'.
As for the difficulty of this problem, it is believed to be difficult as long as you stay within a large prime subgroup; in this case (because you specify a strong prime), you means that you want to make sure that both $x1$ and $x2$ are quadratic residues.
Here's what can go wrong if you don't; an attacker can determine which subgroup any particular element belongs to; if he (for example) determines that $x1$, $x2$ and $y1$ are quadratic nonresidues, and that $y2$ is a quadratic residue, he knows that $r1 \neq r2$. Staying within a prime subgroup prevents this possible information leakage.
• @PaŭloEbermann: in the specific scenario SDL mentioned ($Z^*_p$, where $p$ and $(p-1)/2$ are prime), then it is precisely DDH; unless one of them is $p-1$, then either $x1^k = x2$ or $x2^k = x1$ for some $k$, and it is easy to determine which one it is (by checking Quadratic Redulosity) – poncho Mar 10 '13 at 19:48
• @SDL: sure; $g=x1$, $g^a=x2=x1^k$ (for some unknown $k$), $g^b=y1=x1^{k1}$, $g^c=y2=x2^{k2}=x1^{k\cdot k2}$. Then, if $g^{ab}=g^c$, then $x1^{k \cdot k1} = x1^{k \cdot k2}$, which implies that $k1=k2$. This assumes that that exists a $k$ for which $x1^k=x2$; as per my previous comment, that can be ensured (possibly by swapping x1 and x2) – poncho Mar 11 '13 at 18:31