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 $\mathbb{F}$. We consider the set $F=\{f_0,...,f_{m-1}\}$, where each $latex f_i \in \mathbb{F}[x_0,\dots,x_{n-1}]$. A solution to $latex F$ is any point $x \in \mathbb{F}^n$ 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 $x \in \mathbb{F}^n$ which satisfies the maximum number of polynomials in $F$. Likewise, by Partial Max-PoSSo we denote the problem to return a point $x \in \mathbb{F}^n$ such that for two sets of polynomials $\mathcal{H}$ and $\mathcal{S}$ in $\mathbb{F}[x_0, \dots, x_{n-1}]$, we have $f(x) = 0$ for all $f \in \mathcal{H}$, and the number of polynomials $f \in \mathcal{S}$ with $f(x) = 0$ is maximised. Max-PoSSo is Partial Max-PoSSo with $\mathcal{H} = \varnothing$.

Finally, by Partial Weighted Max-PoSSo we denote the problem to return a point $x \in \mathbb{F}^n$ such that $\forall f \in \mathcal{H}: f(x) = 0$ and $\sum_{f \in \mathcal{S}} \mathcal{C}(f,x)$ is minimized where $\mathcal{C}: f \in \mathcal{S},x \in \mathbb{F}^n \rightarrow \mathbb{R}_{\geq 0}$ is a cost function which returns $0$ if $f(x) = 0$ and some value $> 0$ if $f(x) \neq 0$. Partial Max-PoSSo is Weighted Partial Max-PoSSo where $\mathcal{C}(f,x)$ returns 1 if $f(x) \neq 0$ for all $f$.

It turns out one can solve Partial Weighted Max-PoSSo over $\mathbb{F}_2$ 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.

At Cirencester Julia Borghoff, Lars R. Knudsen and Mathias Stolpe presented their paper on how to express Bivium as a MIP problem. The conversion routines they propose and discuss are more generally applicable than Bivium and thus I wrote a little converter to convert systems of boolean polynomials to a MIP problem. MIP is now relatively well supported in Sage, thanks to the work of Nathann Cohen. Btw. for small scale AES systems the “Integer Adapted Standard Conversion” seems to be better than the “Standard Conversion” method contrary to the results reported in the original paper. There are a few tricks which I didn’t implement in the converter yet, but it should give reasonable results. Oh, the code requires the Christmas edition of Sage aka 4.3.

Cool New Stuff in Recent Sage Releases

Now that Sage 4.3 was released, maybe it’s time to point out some of the cool recent developments. Of course the following list is very very biased.

• libSingular functions interface. We now have some code which makes it possible to call any function available in Singular using the libSingular C wrapper directly, like this.
sage: P = PolynomialRing(GF(127),10,'x')
sage: I = Ideal(P.random_element() for _ in range(3000))
sage: from sage.libs.singular.function import singular_function, lib
sage: groebner = singular_function('groebner')
sage: %time groebner(I)
CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s
[1]

For comparison, the Singular pexpect interface needs almost two seconds for the same task (due to string parsing on both ends, IPC, etc.)

sage:%time groebner_basis()
CPU times: user 0.96 s, sys: 0.24 s, total: 1.21 s
Wall time: 1.92 s
[1]

Michael Brickenstein wrote a lot of this code, so three cheers to him!

• linear algebra over F_2 got better. For once, we implemented vectors over F_2 on top of M4RI matrices (cf. #7715), which makes them much faster. Furthermore, we call more dedicated M4RI functions now instead of the generic slow functions available for all fields (cf. #3684). Finally, asymptotically fast matrix factorisation got faster again. However, we still didn’t switch to this implementation as the default implementation because of the slow-down for sparse-ish matrices: use the algorithm=’pluq’ option to force the new implementation.
• PolyBoRi was updated to version 0.6.3 and the interface received some considerable update too during a visit to Kaiserslautern. Please, please, please report any regressions etc. either to me, to [sage-support] or to [polybori-discuss]. didn’t make it, cf. #7271
• Linear Programming is now available in Sage (though it requires to install at least one optional package). Still, this opens up quite a few possibilities (cf. Nathann Cohen’s tutorial).