Secure blinding factor switching at malicious server-side (Switching in One Time pad)

Question

Suppose all the values and operations are defined over a finite field $\mathbb{F}_p$ where $p$ is a large prime number. Assume all values are non-zero. Here $(z)^{-1}$ denotes multiplicative inverse of value $z$.

We give away the values $v_1$ and $v_2$ to an adversary and ask him to compute their product:

• $v_1=a\cdot z_1$
• $v_2=b \cdot z_2 \cdot (z_1)^{-1}$

So, the adversary computes $v_3= v_1\cdot v_2=a\cdot b \cdot z_2$.

The values $z_i$ are picked uniformly at random from the field. But $a$ and $b$ are fixed values of the field.

Questions:

1. Given the three values $v_3, v_1$ and $v_2$ can the adversary learn anything about the fixed values $a$ and $b$ (and the $z_i$ values)? If yes/no Why?

   In other worlds, given the above three values, can the adversary infer anything about $a$ and $b$?

2. Let $v_1=a\cdot z_1$ and $v_2=(z_1)^{-1}\cdot z_2$.

   If we give $v_1$ and $v_2$ to the adversary and ask him to compute their product: $v_3=v_1\cdot v_2=a\cdot z_2$ would it learn the secret value $a$ (and $z_i$ values)?

Answer 1

I'll answer question 2, leaving the first as an exercise to the reader. I'll do this on intuitive grounds, rather than using explicit conditional probabilities.

The adversary is free to compute $v_1\cdot v_2$ regardless of what we ask, therefore removing everything about that and $v_3$ does not change the problem, which reduces to:

We somewhat have chosen some $a\in\mathbb F_p$. We draw a random uniform secret $z_1\in\mathbb F_p^*$ (so that it's inverse ${z_1}^{-1}$ is well-defined) and a random uniform secret $z_2\in\mathbb F_p$, and compute and reveal $v_1=a\cdot z_1$ and $v_2={z_1}^{-1}\cdot z_2$ to the adversary; what does that reveal about $a$?

Lemma 1: for unknown $u\in\mathbb F_p^*$, drawing a random uniform secret $z\in\mathbb F_p$, and revealing $v=u\cdot z$, reveals nothing about $u$.

Lemma 2: for unknown $u\in\mathbb F_p^*$, drawing a random uniform secret $z\in\mathbb F_p^*$, and revealing $v=u\cdot z$, reveals nothing about $u$.

Proof follows from the fact that $z\to u\cdot z$ is a mapping over $\mathbb F_p$ (for lemma 1) or over $\mathbb F_p^*$ (for lemma 2).

Notice that neither $v_2$ nor $z_2$ are involved when we compute and reveal $v_1=a\cdot z_1$. Therefore, we can consider in isolation the part of the protocol where we draw a random uniform secret $z_2\in\mathbb F_p$ and reveal $v_2={z_1}^{-1}\cdot z_2$. We apply lemma 1 with $u={z_1}^{-1}$ (which belongs to $\mathbb F_p^*$), and conclude that revealing $v_2$ reveals nothing about ${z_1}^{-1}$, hence nothing about $z_1$.

Thus the part of the protocol where we compute and reveal $v_2={z_1}^{-1}\cdot z_2$ has revealed nothing about any quantity in the part of the protocol where we compute and reveal $v_1=a\cdot z_1$. If our choice of $a$ was not zero, by lemma 2, that part of the protocol has revealed nothing about $a$. If our choice of $a$ was $0$, $v_1$ will be $0$.

Hence the answer to question 2 is: the protocol reveals precisely whether $a=0$ or not. No other information about $a$ leaks.

With the statement disallowing $z_1=0$ (or if we reject that as having vanishing odds since $p$ is large), it can be shown that no (or vanishingly few) information about $z_1$ in isolation leaks, and that the only (or almost the only) information that leaks about $z_2$ in isolation is whether $z_2=0$ hold.