This question is about polynomial interpolation and security.

Please consider a scenario where we have a polynomial $f$, one of whose roots is $a$. We evaluate it at some $\textbf{x}=(x_0,\ldots,x_n)$ and this yields $\textbf{y}=(y_0,\ldots,y_n)$, where $y_i=f(x_i)$. We shuffle the elements in $\textbf{y}$. Then we give $\textbf{x}$ and the shuffled $\textbf{y}$ to an untrusted server.

The server may try to add some more roots to it by multiplying elements in $\textbf{y}$ by some elements of its choice. Note that the server does not know the original ordering of $\textbf{y}$ and it does not know $a$, too. So at any point in time we can download $\textbf{y}$ and un-shuffle it then check whether $a$ is among the roots. If it is correct then the elements in $\textbf{y}$ with high probability are remained intact (i.e. the server did not changed them).

Question: What is the probability that the server adds some extra roots without knowing the original order of elements? So we get $a$ among the other roots but the server adds more roots too.

TBC: In practice we have a polynomial ring $f$ defined over $\mathbb{Z}_p$ for a prime number $p$.

  • 1
    $\begingroup$ When you say you evaluate $f$ at $x$, do you mean that $f:\mathbb{R} \to \mathbb{R}$ is a 1-D polynomial and $y_i=f(x_i)$ or that $f:\mathbb{R}^n \to \mathbb{R}^n$ is a vector-valued polynomial which takes $n$ inputs and returns $n$ outputs? $\endgroup$ – gt6989b Jul 31 '15 at 12:44
  • $\begingroup$ @gt6989b $y_i=f(x_i)$. I'll edit the question. $\endgroup$ – user13676 Jul 31 '15 at 12:47
  • $\begingroup$ "The server may try to add some more roots to it by adding or multiplying elements in $\textbf{y}$ by some elements of its choice." I don't understand that at all. A root is a number $a$ for which $f(a)=0$. You're saying those can be added by adding or multiplying elements of $\textbf{y}$. How does that work? Then you say we can download $\mathbf{y}$ and check whether $a$ is among the roots. What does the information in $\textbf{y}$ have to do with whether $a$ is among the roots? $\endgroup$ – Michael Hardy Jul 31 '15 at 12:47
  • $\begingroup$ @MichaelHardy We initially have $f(x)=(x-a)g(x)$. where $g(x)$ can have some roots. Consider a polynomial $f'(x)=(x-z)$. We evaluate $f'$ at the elements in $\textbf{x}$ so we would have $\textbf{y}'=(y'_0,...,y'_n)$. If we do $\textbf{y}' \cdot \textbf{y}$ component-wise, then we interpolate, we would have a polynomial $f''=f\cdot f'$. $\endgroup$ – user13676 Jul 31 '15 at 12:54
  • $\begingroup$ @MichaelHardy For this reason we shuffle it to prevent the server from doing that. The question is there any chance that the server can do the same multiplication without knowing the original ordering of elements? In the above comment note that $f''$ contains the roots of $f$ and $f'$. $\endgroup$ – user13676 Jul 31 '15 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.