1
$\begingroup$

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 )

Improve this question
$\endgroup$
2
  • 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, 2014 at 22:26
  • $\begingroup$ thanks @poncho, and you're right.. it should be a field.. $\endgroup$
    – Subhayan
    May 2, 2014 at 22:34

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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