International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: New Technique for Solving Sparse Equation Systems

HÃ¥vard Raddum
Igor Semaev
Search ePrint
Search Google
Abstract: Most of the recent cryptanalysis on symmetric key ciphers have focused on algebraic attacks. The cipher being attacked is represented as a non-linear equation system, and various techniques (Buchberger, F4/F5, XL, XSL) can be tried in order to solve the system, thus breaking the cipher. The success of these attacks has been limited so far. In this paper we take a different approach to the problem of solving non-linear equation systems, and propose a new method for solving them. Our method differs from the others in that the equations are not represented as multivariate polynomials, and that the core of the algorithm for finding the solution can be seen as message-passing on a graph. Bounds on the complexities for the main algorithms are presented and they compare favorably with the known bounds. The methods have also been tested on reduced-round versions of DES with good results. This paper was posted on ECRYPT's STVL website on January 16th 2006.
  title={New Technique for Solving Sparse Equation Systems},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / sparse algebraic equations, block ciphers, algebraic attacks, DES},
  note={Published on internal ECRYPT website 13500 received 18 Dec 2006},
  author={HÃ¥vard Raddum and Igor Semaev},