Small Linearization: Memory Friendly Solving of Non-Linear Equations over Finite Fields.
Christopher Wolf, Enrico Thomae · 2011
Solving non-linear and in particular Multivariate Quadratic equations over nite elds is an important cryptanalytic problem. Apart from needing exponential time in general, we also need very large amounts of memory, namely ≈ Nn 2 for n variables, solving degree D, and N ≈ n D. Exploiting systematic structures in the linearization matrix, we show how we can reduce this amount of memory by n 2 to ≈ N. For practical problems, this is a signi cant improvement and allows to t the overall algorithm in the RAM of one machine, even for larger values of n. Hence we call our technique Small Linearization (sℓ). We achieve this by introducing a probabilistic version of the F5 criterion. It allows us to replace (sparse) Gaussian Elimination by black box methods for solving the underlying linear algebra problem. Therefore, we achive a drastic reduction in the algorithm's memory requirements. In addition, Small Linearization allows for far easier parallelization than algorithms using structured Gauss.