1
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ What's the problem you're trying to solve? From the title you gave your question, you're thinking of some specific use - I have no idea what that is. $\endgroup$ – poncho Feb 3 '16 at 18:58
  • $\begingroup$ @poncho assume $v_1$ is stored in the server. I want to securely ask him to compute $a.b$ but it should not learn anything about $a$ and $b$. So later on I send valu $v_2$ and ask him to compute $v_1\cdot v_2$. But As I said $a, b$ and $a\cdot b$ must remain secret in the server. $\endgroup$ – user153465 Feb 3 '16 at 19:00
  • $\begingroup$ @poncho So I want to both switch the blinding factor $z_1$ (like proxy re-encryption) and multiply value $a$ by $b$. $\endgroup$ – user153465 Feb 3 '16 at 19:21
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the answer, it's very precise. I'm wondering why you did not discuss about $v_3$ in your answer. Why cannot we say $v_3$ contains random value $z_2$ that has already been used in $v_2$. Therefore, according to one-time-pad it may leak information as the random value has been used twice. $\endgroup$ – user153465 Feb 4 '16 at 9:26
  • $\begingroup$ @user153465: the second paragraph in the answer tries to address that. The adversary is free to compute any function of $v_1$ and $v_2$, like $v_4(v_1,v_2)=(v_1+v_2)^{v_1-v_2}$, or $v_3(v_1,v_2)=v_1\cdot v_2$, anything goes, that has no influence on the demonstration given. This is just extra added to the question's statement, obscuring it, that we want to get rid of to focus on the expressions involving $a$, or $z_1$, $z_2$ or other things not known to the adversary. $\endgroup$ – fgrieu Feb 4 '16 at 21:44

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.