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.

Improve this question
$\endgroup$
3
  • $\begingroup$ $K$ seems to be superfluous, as it can be computed from $I$, $w$ and $c$. $\endgroup$
    – cygnusv
    Oct 15, 2015 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, 2015 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, 2015 at 16:13

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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, 2016 at 17:48
  • $\begingroup$ So my question is Why does not $K$ leak any information about the secret values? $\endgroup$
    – user153465
    Feb 3, 2016 at 17:49
  • $\begingroup$ @user153465, since $K$ is calculated from the other values, it cannot leak any extra information. $\endgroup$
    – otus
    Feb 3, 2016 at 19:30

Your Answer

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

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