6
$\begingroup$

I have two secret values $a$ and $b$ (i.e. they are arbitrary values). I mask them as follow:

$v_1=r_1a+r_2$

$v_2=r_1(b-a)$

where $r_1$ and $r_2$ are uniformly random values. I send $v_1$ and $v_2$ to a malicious server, and ask him to compute $v_1+v_2=r_1b+r_2$


Question: Given $v_1$ and $v_2$, can the server learn anything about $a$ and $b$?


Note: We know that if the server learns $r_1$ or $r_2$ it can figure out the values $a$ and $b$ too.

Edit: I consider modular operations, so they are done mod $p$ where $p$ is a large prime number. So $r_i$ is picked uniformly at random from the field $\mathbb{F}_p$

$\endgroup$
7
$\begingroup$

Given $v_1$ and $v_2$, can the server learn anything about $a$ and $b$?

Yes, they can (with high probability) determine whether $a = b$; if $v_2 = 0$, then either $r_1 = 0$ or $a = b$; given that $r_1 = 0$ occurs with probability $1/p$, the attacker can conclude that $a = b$.

Now, that's the only thing the attacker can learn; for any observed $v_1, v_2$, then for any $a, b$ pair with $a \ne b$, there is a unique $r_1, r_2$ pair that makes it work. As $r_1, r_2$ are selected randomly and uniformly, the attacker gets no information on what the actual $a, b$ pair is.

$\endgroup$
  • $\begingroup$ Thank you for the answer, but I'm still a bit confused. What if we pick $r_i$'s unifromly random but with the condition that $v_i\neq 0$ (e.g. using rejection sampling) . When exactly cannot the attacker learn anything? $\endgroup$ – user153465 Dec 14 '15 at 19:25
  • 1
    $\begingroup$ @user153465 when $a == b$ the adversary learns this, and only this fact. If $a\neq b$, the adversary learns that $a\neq b$, but can learn nothing else about $a$ and $b$. $\endgroup$ – mikeazo Dec 14 '15 at 19:27
  • $\begingroup$ @user153465: if $a = b$, then your rejection sampling technique would infinite loop (as $v_2$ will always be 0, no matter what you select for $r_1, r_2$). $\endgroup$ – poncho Dec 14 '15 at 19:44
  • $\begingroup$ @poncho It is still not completely clear to me why the adversary cannot learn anything when $a\neq b$ and $r_i\neq 0$. value $v_1$ is masked by $r_2$, value $v_2$ is masked by $r_1$. Up to this point each random value $r_i$ is used once. But $v_1+v_2=r_1b+r_2$ is masked by both $r_1$ and $r_2$ where they have already been "used". How can we prove that $v_1+v_2$ does not leak any information? $\endgroup$ – user153465 Dec 22 '15 at 16:08
  • $\begingroup$ @user153465: it's informational theoretic; if $r_1, r_2$ is selected in a manner that is indistinguishable from random, then the publishing of the $v_1, v_2$ pair does not given any information to the attacker about the probability of any particular $a, b$ pair that he did not already have. This is precisely the same logic that states that OTP is secure (that is, does not leak any information); that given a ciphertext, then for any plaintext, there is a unique OTP value that makes it work. $\endgroup$ – poncho Dec 22 '15 at 16:20
2
$\begingroup$

The adversary can learn whether or not $a$ and $b$ are equivalent (with high probablility). All other information is protected.

I asked in the comments whether nor not a finite field was used or if we were working in the integers. This is important, because in the unsigned (positive) integers, the adversary can learn order. Since he has $r_1a+r_2$ and can compute $r_1b+r_2$, he has an ordering. Thus, by comparing $v_1$ and this value, the adversary knows the ordering of $a$ and $b$.

$\endgroup$
  • $\begingroup$ Actually, this protocol doesn't work with the integers, as it is impossible to select a random integer with a uniform distribution (!). In any case, comparing $r_1a + r_2$ with $r_1b + r_2$ tells us nothing if we don't know the sign of $r_1$ $\endgroup$ – poncho Dec 14 '15 at 19:17
  • $\begingroup$ That's true. Especially about the sign. Hmm, how to salvage :) $\endgroup$ – mikeazo Dec 14 '15 at 19:22

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.