Paper 2009/252

Sparse Boolean equations and circuit lattices

Igor Semaev

Abstract

A system of Boolean equations is called sparse if each equation depends on a small number of variables. Finding efficiently solutions to the system is an underlying hard problem in the cryptanalysis of modern ciphers. In this paper we study new properties of the Agreeing Algorithm, which was earlier designed to solve such equations. Then we show that mathematical description of the Algorithm is translated straight into the language of electric wires and switches. Applications to the DES and the Triple DES are discussed. The new approach, at least theoretically, allows a faster key-rejecting in brute-force than with Copacobana.

Note: a reference has been added

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. modified version of the paper was presented at WCC09
Keywords
sparse Boolean equationsequations graphelectrical circuitsswitches
Contact author(s)
igor @ ii uib no
History
2009-07-27: revised
2009-06-01: received
See all versions
Short URL
https://ia.cr/2009/252
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/252,
      author = {Igor Semaev},
      title = {Sparse Boolean equations and circuit lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2009/252},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/252}},
      url = {https://eprint.iacr.org/2009/252}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.