Scenario (1)
We define the polynomial ring $R[x]$ consist of all polynomial with coefficients from $\mathbb Z_p$, where $p$ is a prime number. Let $P_i$ be a polynomial such that $P_i \in R[x]$. We evaluate $P_1$ at many $X= (x_1,...,x_n)$ to obtain $Y^{(1)}=(y_1,...,y_n)$, where $n$ can we very large and far more greater than $d+1$, where $d$ is the polynomial degree. We multiply each element in $Y^{(1)}$ by the distinct value chosen uniformly at random from $\mathbb Z_p$, and we denote the result by $Y'^{(1)}=(y_1 \times r_1,...,y_n \times r_n)$, where $r_i$ are random value picked uniformly from $\mathbb Z_p$. The roots of this polynomial matter to us, therefore if one can recover the original polynomial, $P_1$, or by any means he recovers the root(s) (or any knowledge of the roots) our protocol is broken. We publish the $X= (x_1,...,x_n)$ and $Y'^{(1)}$, so anybody can access them (including those who wants to try to figure out the original polynomial and its roots).
Questions 1:
- Given $X$ and $Y'^{(1)}$'s, can anybody deduce any information about the original polynomial (e.g. the roots of the polynomial or the degree of the polynomial, etc)?
Scenario (2)
We have many (millions) of polynomials $P_i$ and we evaluate all of them at the same $X= (x_1,...,x_n)$, to obtain $Y^{(1)},..., Y^{(n)}$. Similar to the scenario (1), we multiply each element in $Y^{(i)}$ by a distinct uniformly at random value $r_i$ (i.e. note all $r_i$'s are random for all elements in all $Y_i$'s) to obtain $Y'^{(1)},..., Y'^{(n)}$.
Questions 2:
- Given $X$ and all $Y'^{(i)}$, can anybody deduce any information about the original polynomial (e.g. the root(s) or the degree of these polynomials)?
Remark: The main reason that the scenario(2) is different than (1) is that the $Y'^{(i)}$'s are somehow linked to each other, as all are the result of evaluation of different polynomials at the same $X$ values. So this may give enough advantage to whoever wants to figure out some information about the original polynomials.
Question 3: If we evaluate a polynomial on some $X$'s to obtain some $Y$ values, Why multiplying $Y$'s by distinct random values is not equal to multiplying the original polynomial by another polynomial?
Question 4: Assume we have $f(x)=(x−1)(x−3)$ interpolate at $X(10,11,12,13,14)$ to obtain $Y=(63,80,99,120,156)$ pick some random value $r=(2,7,6,8,10)$ and compute $Y′=(126,560,594,960,1430)$. Pick prime $p$ at your choice. So we should be able to interpolate a polynomial with $Y′$ and $X$. This polynomial should have some roots including $1$ and $3$. But in practice it is not right. Many thanks