2
$\begingroup$

Assume all values are defined over a field $\mathbb{F}_p$ where $p$ is a large prime number.

Given a fixed value $a,b$ we compute $v_i=a\cdot b+r_i$, where $r_i$ is picked uniformly at random from the field. For the sake of simplicity let all the values be none zero.

Assume the adversary knows $b$.

Question 1: Given $v_i$, can the adversary learn anything about $a$ (or $r_i$)?


Assume $p(x)$ is a monic polynomial whose coefficients are picked uniformly at random from the field. Let $x=\{x_1,x_2\}$ where $x_i$ are public values. Let $b_1$ and $b_2$ be known by the adversary. By $p(x_i)$, we mean polynomial is evaluated at $x_i$.

We compute $v_1=p(x_1)\cdot b_1+r_1$ and $v_2=p(x_2)\cdot b_2+r_2$, where $r_i$ are picked unifromly at random.

Question 2: Given $v_1$ and $v_2$ can the adversary learn anything about $p(x)$ (or $r_i$)?

Please note that the adversary knows $x_i$.

$\endgroup$
1
$\begingroup$

To make sure the values of a uniformly chosen random polynomial in $F_p[x]$ are uniformly distributed, you need to impose a maximum degree for the polynomial, since there is no uniform distribution on a countably infinite space.

Having done this and ensuring the uniformity of the polynomial values, your questions boil down to questioning the uniformity of and independence of quantities like $$a+Z$$ and pairs $$(aZ+W,aZ'+W')$$ where $Z,W,Z',W'$ are uniform and pairwise independent. And they are, since linear polynomials over $F_p$ are permutation polynomials.

To clarify, for both questions, the adversary cannot learn anything about the quantity of concern, since it is an independent random variable from the quantities they have access to. For example, $p(\cdot)$ being uniformly chosen means $p(x_1)$ is uniformly distributed and when $r_1$ which is also uniform is added to it $b_1 p(x_1)+r_1$ is distributed like $aZ+W$, which is itself uniform.

$\endgroup$
  • $\begingroup$ Could you please clarify what the answer to each question is? $\endgroup$ – user153465 Aug 31 '16 at 4:07
  • $\begingroup$ @tylo So what your answer would be to each of the above questions? thanks. $\endgroup$ – user153465 Aug 31 '16 at 13:26
  • $\begingroup$ @user153465 Well, your first construction is just a modified OTP for always the same value, which you call $ab$. The value $b$ plays no role at all. After looking at the construction again, the second is basically the same, just unnecessarily complicated. You could just give him random values and declare your polynomial was $p(x) = 0$. I will remove my earlier comments, as they don't actually matter. The real question is: What is the goal of this? It doesn't really make sense at the moment. $\endgroup$ – tylo Aug 31 '16 at 17:41
  • $\begingroup$ @tylo In the first question, $b$ is known to the adversary. Also $a$ is a fixed value (and it is not a random value) but $r_i$ is a one time pad. So my question is that given $v_i$ and $b$ can the adversary learn the message $a$ (or $r_i$)? (assume $a$ is a message), but the adversary only knows $b$. $\endgroup$ – user153465 Aug 31 '16 at 17:55
  • $\begingroup$ The value $b$ does not play any role at all. Only the value $ab$. You could also pick a arbitrary value $ab$ , a random value $b$, and then calculate $a = ab/b$ afterwards. Since the values $ab$ and $b$ are independent variables, they hold no information about the other. Giving the attacker $b$ is therefore irrelevant. $\endgroup$ – tylo Aug 31 '16 at 18:02

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.