Paper 2011/669

Small Linearization: Memory Friendly Solving of Non-Linear Equations over Finite Fields

Christopher Wolf and Enrico Thomae

Abstract

Solving non-linear and in particular Multivariate Quadratic equations over finite fields is an important cryptanalytic problem. Apart from needing exponential time in general, we also need very large amounts of memory, namely $\approx Nn^2$ for $n$ variables, solving degree $D$, and $N \approx n^D$. Exploiting systematic structures in the linearization matrix, we show how we can reduce this amount of memory by $n^2$ to $\approx N$. For practical problems, this is a significant improvement and allows to fit the overall algorithm in the RAM of \emph{one} machine, even for larger values of $n$. Hence we call our technique Small Linearization (sl). We achieve this by introducing a probabilistic version of the F$_5$ 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
MQ problemAlgebraic AttacksEquation SolverF5Buchberger
Contact author(s)
chris @ christopher-wolf de
enrico thomae @ rub de
History
2011-12-16: received
Short URL
https://ia.cr/2011/669
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/669,
      author = {Christopher Wolf and Enrico Thomae},
      title = {Small Linearization: Memory Friendly Solving of Non-Linear Equations over Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2011/669},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/669}},
      url = {https://eprint.iacr.org/2011/669}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.