On the complexity of solving quadratic Boolean systems

详细信息    查看全文

• 作者：Magali Bardet^a ; ^{magali.bardet@univ-rouen.fr} ; Jean-Charles Faug&egrave ; re^b ; ^c ; ^d ; ^{Jean-Charles.Faugere@inria.fr} ; Bruno Salvy^e ; ^{bruno.salvy@inria.fr} ; Pierre-Jean Spaenlehauer^b ; ^c ; ^d ; ^{pierre-jean.spaenlehauer@lip6.fr}
• 关键词：Boolean quadratic system ; Grö ; bner bases ; Complexity ; Semi-regularity ; Multivariate cryptography
• 刊名：Journal of Complexity
• 出版年：2013
• 出版时间：February, 2013
• 年：2013
• 卷：29
• 期：1
• 页码：53-75
• 全文大小：628 K

文摘

A fundamental problem in computer science is that of finding all the common zeros of quadratic polynomials in unknowns over . The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 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. We show that, under precise algebraic assumptions on the input system, the deterministic variant of our algorithm has complexity bounded by when , while a probabilistic variant of the Las Vegas type has expected complexity . 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.