Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
1  
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
    
Great pointer! thanks! –  SDL Mar 11 '13 at 17:25

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Is this really equivalent to DDH? To me it seems like a bit more general case. –  Paŭlo Ebermann Mar 10 '13 at 18:00
    
@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
    
@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? –  SDL Mar 11 '13 at 17:16
    
@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
    
@poncho: Thanks –  SDL Mar 11 '13 at 22:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.