Cryptology ePrint Archive: Report 2007/285

Solving MRHS linear equations

H{\aa}vard Raddum and Igor Semaev

Abstract: A new method for solving algebraic equation systems common in cryptanalysis is proposed. Our method differs from the others in that the equations are not represented as multivariate polynomials, but as a system of Multiple Right Hand Sides linear equations. The method was tested on scaled versions of the AES. The results overcome significantly what was previously achieved with Gr\"{o}bner Basis related algorithms.

Category / Keywords: secret-key cryptography / Multiple Right Hand Sides linear equations, algebraic

Publication Info: Extended Abstract in Proceedings of WCC 2007, Inria, France, pp.323-332

Date: received 25 Jul 2007, last revised 28 Aug 2007

Contact author: igor at ii uib no

Available formats: PDF | BibTeX Citation

Version: 20070828:131824 (All versions of this report)

Discussion forum: Show discussion | Start new discussion