On the Complexity of Solving Quadratic Boolean Systems

Magali Bardet 1 Jean-Charles Faugère 2 Bruno Salvy 3 Pierre-Jean Spaenlehauer 2
1 C&A - Combinatoire et algorithmes
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : A fundamental problem in computer science is to find all the common zeroes of $m$ quadratic polynomials in $n$ unknowns over $\mathbb{F}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in $4\log_2 n\,2^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. Under precise algebraic assumptions, we show that the deterministic variant of our algorithm has complexity bounded by $O(2^{0.841n})$ when $m=n$, while a probabilistic variant of the Las Vegas type has expected complexity $O(2^{0.792n})$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to~1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as~200, and thus very relevant for cryptographic applications.
Type de document :
Article dans une revue
Journal of Complexity, Elsevier, 2013, 29 (1), pp.53-75. <10.1016/j.jco.2012.07.001>
Liste complète des métadonnées

Contributeur : Pierre-Jean Spaenlehauer <>
Soumis le : lundi 2 janvier 2012 - 10:43:03
Dernière modification le : mercredi 27 juillet 2016 - 14:48:48




Magali Bardet, Jean-Charles Faugère, Bruno Salvy, Pierre-Jean Spaenlehauer. On the Complexity of Solving Quadratic Boolean Systems. Journal of Complexity, Elsevier, 2013, 29 (1), pp.53-75. <10.1016/j.jco.2012.07.001>. <hal-00655745>



Consultations de la notice