Solving MRHS linear equations

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

You are looking at a specific version 20070828:131824 of this paper. See the latest version.

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