# Data Leakage and Data Switching

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$

## 2 Answers

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.

• 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? – user153465 Dec 14 '15 at 19:25
• @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$. – mikeazo Dec 14 '15 at 19:27
• @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$). – poncho Dec 14 '15 at 19:44
• @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? – user153465 Dec 22 '15 at 16:08
• @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. – poncho Dec 22 '15 at 16:20

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

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