Nonlinear Phenomena in Complex Systems, 2014, Vol.17, No.3, pp.242-252

NONLINEAR PHENOMENA IN COMPLEX SYSTEMS
An Interdisciplinary Journal

2014, Vol.17, No.3, pp.242-252

On Boolean Ideals and Varieties with Application to Algebraic Attacks
A. G. Rostovtsev and A. A. Mizyukin

To find a symmetric cipher key is to solve the zero ideal of a specified set of polynomials. It is shown that the complexity of solutions can be reduced if the exact or approximate basis of the ideal substitution is defined by short polynomials. The accuracy of short basis polynomials can be improved by an affine change of variables. Two methods are proposed for solving systems of Boolean equations with the use of auxiliary short polynomials.

Key words: cipher, polynomial ring, ideal, variety, Groebner basis

Full text: Acrobat PDF (139KB) Open Access