Solving MRHS linear equations

Håvard Raddum; Igor Semaev

Paper 2007/285 Original: eprint.iacr.org/2007/285 ↗

Solving MRHS linear equations

Håvard Raddum

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: Preprint.
History: 2007-08-28: last updated; 2007-08-07: published
Short URL: https://ia.cr/2007/285
License: https://creativecommons.org/licenses/by/4.0/

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}
}