# find $x$, given $\{c_ix = k_i + y_i\}_{i=[1,n]}$

Given

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

-
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. –  poncho May 2 '14 at 22:26
thanks @poncho, and you're right.. it should be a field.. –  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$.

-
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. :) –  Subhayan May 2 '14 at 23:02
@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. –  poncho May 3 '14 at 0:21