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

2 Answers 2

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$
7
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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$
2
  • $\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, 2015 at 19:17
  • $\begingroup$ That's true. Especially about the sign. Hmm, how to salvage :) $\endgroup$
    – mikeazo
    Dec 14, 2015 at 19:22

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.