Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / sparse algebraic equations, block ciphers, algebraic attacks, DES

Publication Info: Published on internal ECRYPT website

Date: received 18 Dec 2006

Contact author: hra081 at uib no

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20061224:125740 (All versions of this report)

Discussion forum: Show discussion | Start new discussion