International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Solving MRHS linear equations

Authors:
Håvard Raddum
Igor Semaev
Download:
URL: http://eprint.iacr.org/2007/285
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13566,
  title={Solving MRHS linear equations},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Multiple Right Hand Sides linear equations, algebraic},
  url={http://eprint.iacr.org/2007/285},
  note={Extended Abstract in Proceedings of WCC 2007, Inria, France, pp.323-332 igor@ii.uib.no 13753 received 25 Jul 2007, last revised 28 Aug 2007},
  author={Håvard Raddum and Igor Semaev},
  year=2007
}