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 ![\mathbb{F}[x_0, \dots, x_{n-1}]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D%5Bx_0%2C+%5Cdots%2C+x_%7Bn-1%7D%5D&bg=ffffff&fg=1a1a1a&s=0 "\mathbb{F}[x_0, \dots, x_{n-1}]")
, 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.
Like this:
Like Loading...
Related
