Polynomial Interpolation and Security

Let polynomial $P$ be $P(x)=g(x).(x−β)$, where $g$ is a polynomial and $\beta \leftarrow \mathbb{F}_p$. We evaluate $P$ at some $\textbf{x}=(x_1,..,x_n)$. This gives us $\textbf{y}=(y_1,..,y_n)$. Assume some of $y_i$’s are accidentally changed to some random values $y′_i$’s. Now we interpolate $(x_1,y_1),…,(x_i,y′_i),..(x_j,y′_j),…(x_n,y_n)$, to get a polynomial $P′$.

My question: What is the probability that $P′$ has the root β?

Definitions: $y_i$ is defined as $P(x_i)=y_i$, $x_i \neq0$ , $x_i\neq x_j$, the polynomials, $x_i$’s and $y_i$’s are defined over finite field $\mathbb{F}_p$ for a large prime $p$.

Solutions Collecting From Web of "Polynomial Interpolation and Security"

The probability is $\frac{1}{p}$.

One way to see this is to imagine that instead of $(x_n,y_n’)$ you take $(\beta,0)$ as an interpolation point. Then you get a unique polynomial $\tilde{P}$ of degree at most $n-1$ satisfying $\tilde{P}(x_i)=y_i’$ for $i<n$ and $\tilde{P}(\beta)=0$. Let $\tilde{y_n}=\tilde{P}(x_n)$. You know that $P’$ has degree at most $n-1$ and satisfies $P'(x_i)=y_i’$ for all $i$, thus in particular for $i<n$. It follows from the uniqueness of interpolation polynomials that $P'(\beta)=0$ iff $P’=\tilde{P}$ iff $\tilde{y}_n=\tilde{P}(x_n)=y_n’$, and since $y_n’$ is taken uniformly randomly in $\mathbb{F}_p$, the probability that $y_n’=\tilde{y}_n$ is $\frac{1}{p}$.

Note : I treated the problem like all $y_i$ had been changed to values $y_i’$, which are possibly equal to $y_i$.