5
$\begingroup$

Consider we have a fixed value $x$. We pick values $ r_1,r_2,z\leftarrow \mathbb{F}_p$, where $p$ is a large prime number, and it is public. So $r_1,r_2,z$ are uniformly random values.

We compute four values as below:

  1. $u_1=r_1\cdot x,\ \ w_1=r_1\cdot z$
  2. $u_2=r_2\cdot x,\ \ w_2=r_2\cdot z$

Question: Do $u_1,u_2,w_1,w_2$ leak information about values $x,r_1,z,r_2$?

In other words: can an adversary learn about the values $x,r_1,z,r_2$ when given $u_1,u_2,w_1,w_2$?

Edit: $u_i, w_i\neq 0$

$\endgroup$
  • $\begingroup$ What are you trying to accomplish with this? In particular, which of the values $x$, $z$, $r_1$ and $r_2$ do you wish to keep secret, and why? $\endgroup$ – Ilmari Karonen Sep 17 '15 at 14:49
  • 1
    $\begingroup$ The notation is terrible; swapping $u_2$ and $w_1$ would have been more coherent. $\endgroup$ – fgrieu Sep 17 '15 at 14:50
  • 2
    $\begingroup$ @fgrieu: That's a good suggestion. I've edited the question and my answer to do just that. $\endgroup$ – Ilmari Karonen Sep 17 '15 at 21:30
  • $\begingroup$ @IlmariKaronen I want to keep $x$ secret . To this end I blind $x$ with the random value $r_1$. In my protocol $u_1$ is given to the adversary to switch a value. After switching we have $w_1$. As you can see in step (1) we have both $u_1$ and $w_1$. Next time we can change the random value to $r_2$. Again $u_2$ is given to the adversary.... However, as you know, in order to keep $x$ secret the rest of random values $r_1,r_2,z$ should be kept secret, too. $\endgroup$ – user13676 Sep 18 '15 at 9:29
  • $\begingroup$ If only two of u1,u2,w1,w2 are equal to 0, then an adversary learns one of the values x,r1,r2,z. $\endgroup$ – Florian Bourse Sep 18 '15 at 15:28
6
$\begingroup$

Yes, this does leak some information. In fact, just knowing $u_1$ and $w_1$ will allow the attacker to calculate $u_1^{-1} w_1 = x^{-1} z$.* In particular, knowing this value will let the attacker calculate $x$ if they know $z$, or vice versa.

Similarly, knowing $u_1$ and $u_2$ will let the attacker calculate $u_1^{-1} u_2 = r_1^{-1} r_2$. With $u_1$, $w_1$ and $u_2$, they can calculate both of these. (Knowing $w_2$ will not actually add any further information, since it can be calculated from the other values as $u_2 u_1^{-1} w_1 = u_2 x^{-1} z = r_2 z = w_2$.)

Without additional information, however, you cannot work out the exact value of any single parameter. In particular, given any (non-zero) $x$, we can choose $r_1$ and $r_2$ so that $u_1 = r_1x$ and $u_2 = r_2x$ take any values we like, and then further choose $z$ so that $w_1 = r_1z$ takes any value we like; $w_2 = r_2z$ will then equal $u_2 u_1^{-1} w_1$, as it always must.

*) I'm assuming here that all the values are non-zero, and therefore invertible, which they most likely are if they're chosen at random modulo a large prime. You can work out the special cases where some of the values are zero as an exercise yourself, if you like.

$\endgroup$
1
$\begingroup$

As the previous poster says the problem can not be solved if you don't know $x,z,r_1,r_2.$ But the question seems to have some connection with the generalized hidden number problem. In some sense answers the opposite question of the OP. Say that you have an oracle that gives you $r_1,r_2,...,r_{d}$ (polynomial many) uniformly from ${\bf Z}_p$ (so the $r_j$'s are known). Further assume that, you know the $\ell$ most significant bits of all the numbers $w_j=r_j\cdot x \pmod q.$ Then Boneh and Venkatesan proved that you can find $x$ in polynomial time $O(poly(\log{p}))$ for appropriate $d,\ell,p$ (for instance if $d=\ell\approx 2\sqrt{p}$).

$\endgroup$

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.