New Technique for Solving Sparse Equation Systems

Håvard Raddum; Igor Semaev

Paper 2006/475

New Technique for Solving Sparse Equation Systems

Håvard Raddum and Igor Semaev

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.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Published on internal ECRYPT website
Keywords: sparse algebraic equations block ciphers algebraic attacks DES
Contact author(s): hra081 @ uib no
History: 2006-12-24: received
Short URL: https://ia.cr/2006/475
License: CC BY

BibTeX

@misc{cryptoeprint:2006/475,
      author = {Håvard Raddum and Igor Semaev},
      title = {New Technique for Solving Sparse Equation Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2006/475},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/475}},
      url = {https://eprint.iacr.org/2006/475}
}