2
$\begingroup$

Hypothesis: Let $z,a$ be uniformly random elements of a field $\mathbb{F}_p$ where $p$ is a large prime number. Also, let $(-z)$ be additive inverse of $z$.


I have a fixed secret value $x$. I mask it as $I=x+z$ and send it to a semi-honest server.

Later on, I send $w$ and $c=(-z)\cdot w+a$ to the server, and ask it to do as follows: $K=I\cdot w+c=(x+z)\cdot w+(-z)\cdot w+a=wx+a$.

Question: Given $I, w,c$ and $K$, can the server learn anything about $x$?


Note 1: $z,a$ are secret values, too. So if the server learns about them it may learn about $x$.

Note 2: The above scenario is a part of protocol and it may not make sense for the readers at first glance.

$\endgroup$
  • $\begingroup$ $K$ seems to be superfluous, as it can be computed from $I$, $w$ and $c$. $\endgroup$ – cygnusv Oct 15 '15 at 13:11
  • $\begingroup$ @cygnusv Yes, you're right. I wanted to say that $K$ is the final result that the server computes for me. $\endgroup$ – user153465 Oct 15 '15 at 13:13
  • 2
    $\begingroup$ If $w=0$ then $c=a$, but no information about $-z$ and hence $x$ is given by knowing $c$. Otherwise $w\ne 0$ allows you to write $a = c+zw$ as well as $z=w^{-1}(a-c)$ showing that there is a one-to-one correspondence between $a$ and $z$ for any choice of $c$ and $w(\ne 0)$. This is consistent with the fact that both $z$ and $a$ are drawn uniformly from $\mathbb{F}_p$. I do not know now, how to finish the proof that the server learns nothing about $x$, but it should follow from the one-to-one correspondence between $z$ and $a$. $\endgroup$ – j.p. Oct 15 '15 at 16:13
3
$\begingroup$

Server receives three messages:

  1. $I=x+z$. This is the value $x$ encrypted with a one-time pad $z$. The server cannot find $x$ without knowing (something about) $z$.

  2. $w$. This is (presumably) independent of anything secret.

  3. $c=(-z)\cdot w+a$. This is the value $(-z)\cdot w$ encrypted with a one-time pad $a$. The server receives no information about $(-z)\cdot w$ and thus $z$ or $x$ without knowing something about $a$.

Therefore, assuming that $z$ and $a$ are generated randomly just for this instantiation and never reused or revealed, and that $w$ is independent of $x, z, a$, the server learns nothing about $x$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. I'm wondering why you didn't say anything about the result $K=wx+a$. In the result $a$ cannot be considered as a one time pad (as it has been before). $\endgroup$ – user153465 Feb 3 '16 at 17:48
  • $\begingroup$ So my question is Why does not $K$ leak any information about the secret values? $\endgroup$ – user153465 Feb 3 '16 at 17:49
  • $\begingroup$ @user153465, since $K$ is calculated from the other values, it cannot leak any extra information. $\endgroup$ – otus Feb 3 '16 at 19:30

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.