Paper 2012/151

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
AESblock cipherscryptanalysis
Contact author(s)
alexander rostovtsev @ ibks ftk spbstu ru
History
2012-03-22: received
Short URL
https://ia.cr/2012/151
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/151,
      author = {Alexander Rostovtsev and Alexey Mizyukin},
      title = {On Boolean Ideals and Varieties with Application to Algebraic Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2012/151},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/151}},
      url = {https://eprint.iacr.org/2012/151}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.