Solving MRHS linear equations

Håvard Raddum; Igor Semaev

Paper 2007/285

Solving MRHS linear equations

Hå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öbner Basis related algorithms.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Extended Abstract in Proceedings of WCC 2007, Inria, France, pp.323-332
Keywords: Multiple Right Hand Sides linear equations algebraic
Contact author(s): igor @ ii uib no
History: 2007-08-28: revised; 2007-08-07: received; See all versions
Short URL: https://ia.cr/2007/285
License: CC BY

BibTeX

@misc{cryptoeprint:2007/285,
      author = {Håvard Raddum and Igor Semaev},
      title = {Solving {MRHS} linear equations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/285},
      year = {2007},
      url = {https://eprint.iacr.org/2007/285}
}