# 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$.

• $P'$ is the polynomial interpolating the $n$ points in $S$, so it certainly has degree $n-1$ at most. But I don't understand how you choose $\beta$. If it's picked randomly among the elements in your field $\mathbb{F}_p$ there is no reason that it should be a root of $P$... – Arnaud D. Aug 22 '15 at 13:45
• @Arnaud We first define $P$ where $P=g.(x-\beta)$, where $g$ is a polynomial. Then 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 is what is the probability that $P'$ has the root $\beta$. – user13676 Aug 22 '15 at 13:53
• I'm editing the question. – user13676 Aug 22 '15 at 14:00
• Ah I understand better now. Can we assume that we know exactly how many $y_i$'s are changed? Or do we only know that there has been some change, but without any detail? – Arnaud D. Aug 22 '15 at 14:02
• @Arnaud In fact I want it for data integrity check, so we do not know anything about the changes. That is why we insert $\beta$ to let us detect such a change, so we know $\beta$. But I need to know how sure I can be with this check. – user13676 Aug 22 '15 at 14:07

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$.
• What if some of $y_i$'s are changed (e.g. two or three of them)? Am I right that the other unchanged $y_i$'s may increase the chance that $\beta$ appear in the interpolating polynomial's root? – user13676 Aug 22 '15 at 15:11
• @Arnaud Before the clarification that $\deg P = n-1$, it wasn't necessarily true that $\tilde{P}(\beta) = 0$ (for instance, if $\deg P > n$, then just knowing that $P(\beta)=0$ does not imply much about $\tilde{P}(\beta)$ :). – Erick Wong Aug 22 '15 at 15:38
• I will mention that this is kind of trivial in this case (though matches the question); if all of the $y_{i}$ are allowed to change/not change, you are replacing your polynomial $P(x)$ with some random polynomial $P^{\prime}(x)$ of degree at most $n-1$. Because this polynomial is random, the value $P^{\prime}(\beta)$ is also a random element of $\mathbb{F}_{p}$, so probability $P^{\prime}(\beta)=0$ is $1/p$. – Morgan Rodgers Aug 23 '15 at 7:22