1
$\begingroup$

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$?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I believe there are some groups which have this property. I think the lucre paper briefly mentioned them. $\endgroup$
    – CodesInChaos
    Mar 9, 2013 at 15:00

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is this really equivalent to DDH? To me it seems like a bit more general case. $\endgroup$
    – Paŭlo Ebermann
    Mar 10, 2013 at 18:00
  • $\begingroup$ @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) $\endgroup$
    – poncho
    Mar 10, 2013 at 19:48
  • $\begingroup$ @poncho: Could you clarify, in your equivalence between my problem and DDH, which is g,a,b and c from x1,x2,y1,y2,k1,k2? $\endgroup$
    – SDL
    Mar 11, 2013 at 17:16
  • $\begingroup$ @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) $\endgroup$
    – poncho
    Mar 11, 2013 at 18:31

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.