**On Boolean Ideals and Varieties with Application to Algebraic Attacks**

*Alexander Rostovtsev and Alexey Mizyukin*

**Abstract: **Finding the key of symmetric cipher takes computing common zero of polynomials, which define ideal and corresponding variety, usually considered over algebraically closed field. The solution is the point of the variety over prime field; it is defined by a sum of the polynomial ideal and the field ideal that defines prime field. Some authors use partitioning of this sum and reducing syzygies of polynomial ideal modulo field ideal. We generalize this method and consider polynomial ideal as a sum of two ideals, one of them is given by short polynomials, and add this ideal to the field ideal. Syzygies are reduced modulo this sum of ideals. Accuracy of definition of the substitution ideal by short polynomials can be increased using affine equivalence of ideals. This method decreases degree and length of syzygies and reduces complexity of Groebner basis computation.

**Category / Keywords: **secret-key cryptography / AES, block ciphers, cryptanalysis

**Date: **received 22 Mar 2012

**Contact author: **alexander rostovtsev at ibks ftk spbstu ru

**Available format(s): **PDF | BibTeX Citation

**Version: **20120322:213337 (All versions of this report)

**Short URL: **ia.cr/2012/151

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]