$$c_1x = k_1 + y_1 $$ $$c_2x = k_2 + y_2 $$ $$\vdots $$ $$c_nx = k_n + y_n $$

where the values of $\{c_1 \ldots c_n \}$ and $\{ k_1 \ldots k_n \}$ are known, and $x, \{y_1 \ldots y_n \}$ are unknown. $y_i$ is chosen uniformly at random.

We are working in a field of $GF(p)$, so all $c_i, k_i, x, y_i ∈ \mathbb{Z}_p^*$. $p$ is some prime.

From here, how can we recover the value of $x$ ?

(suppose $c_i = c_j$ OR $\ k_i = k_j$ for some $i,j$ that we know )

  • 3
    $\begingroup$ You say you are working in the group $\mathbb{Z}_p^*$, but then you perform both the addition and the multiplication operation; groups only have one operator. Do you really mean that you are working within the field $GF(p)$? Or, do you mean only the nonzero elements of $Z/p$ (and so the addition operation is not formally closed)? I'm asking because I wrote up an answer, and before I posted it, I realized that it depended on what structure you're in. $\endgroup$ – poncho May 2 '14 at 22:26
  • $\begingroup$ thanks @poncho, and you're right.. it should be a field.. $\endgroup$ – Subhayan May 2 '14 at 22:34

There is no way to recover $x$ in this scenario; there is not even a way to say "this value of $x$ is more likely than that value"

One demonstration is that if we attempt to test a particular value $x'$; we can compute the necessary values:

$$y_i = c_i x - k_i$$

However, if all the values $y_i$ are randomly distributed, and given that we have no further restriction of what the values $y_i$ might be, this distribution is no less probable than any other distribution; hence these relations give us no information about $x$.

Since those relations are the only thing we know about $x$, that means we have no criteria to say which values are more or less probable.

This holds true for any sets of values $c_i, k_i$, and specifically if we have $c_i = c_j$ or $k_i = k_j$.

  • $\begingroup$ that was my initial thought on this, another way to look at is probably we have $n$ equations and $n+1$ unknowns.. we can have a reduction, by simply setting $c_i =1$ to show this is not possible.. but well... i was rooting for a break.. i'll see till tom.. else accept this answer. :) $\endgroup$ – Subhayan May 2 '14 at 23:02
  • $\begingroup$ @Subhayan: that's another way of putting it; however, that's less precise, because even though you have only $n$ equations, in theory it could be that all solutions to those equations might share the same $x$ value -- as I show, that doesn't happen here. $\endgroup$ – poncho May 3 '14 at 0:21

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.