Polynomial System Solving with Noise

The reason I became somewhat interested in mixed integer programming is that it is one way of solving polynomial systems which are noisy. These kind of polynomial systems pop up in crypto all over the place but so far — to my knowledge — they have not been studied extensively. In order to clarify what is meant by “polynomial system solving with noise”, we can define a familiy of Max-PoSSo problems similar to the Max-SAT family of problems (in fact, you can reduce Max-PoSSo to Max-SAT).

Polynomial system solving (PoSSo) is the problem of finding a solution to a system of polynomial equations over some field . We consider the set , where each $latex f_i \in \mathbb{F}[x_0,\dots,x_{n-1}]$. A solution to $latex F$ is any point such that $latex \forall f \in F$, we have $latex f(x) = 0$. Note that we restrict ourselves to solutions in the base field in this context.

Then by Max-PoSSo we denote the problem of finding any which satisfies the maximum number of polynomials in . Likewise, by Partial Max-PoSSo we denote the problem to return a point such that for two sets of polynomials and $\mathcal{S}$ in , we have for all , and the number of polynomials with is maximised. Max-PoSSo is Partial Max-PoSSo with .

Finally, by Partial Weighted Max-PoSSo we denote the problem to return a point such that and is minimized where is a cost function which returns if and some value if . Partial Max-PoSSo is Weighted Partial Max-PoSSo where returns 1 if for all .

It turns out one can solve Partial Weighted Max-PoSSo over using mixed integer programming. Recently, Carlos and I have been busy applying these ideas to the cold boot problem, with reasonable success. An extended abstract of our work is available here. Two sets of slides discussing our techniques are also available here and here.