You are looking at a specific version 20060724:100012 of this paper. See the latest version.

Paper 2006/251

Accelerating Cryptanalysis with the Method of Four Russians

Gregory V. Bard

Abstract

Solving a dense linear system of boolean equations is the final step of several cryptanalytic attacks. Examples include stream cipher cryptanalysis via XL and related algorithms, integer factorization, and attacks on the HFE public-key cryptosystem. While both Gaussian Elimination and Strassen’s Algorithm have been proposed as methods, this paper specifies an algorithm that is much faster than both in practice. Performance is formally modeled, and experimental running times are provided, including for the optimal setting of the algorithm’s parameter. The consequences for published attacks on systems are also provided. The algorithm is named Method of Four Russians for Inversion (M4RI), in honor of the matrix multiplication algorithm from which it emerged, the Method of Four Russians Multiplication (M4RM).

Note: Thanks!

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Submitted to a Conference.
Keywords
Algebraic CryptanalysisFactoringBoolean MatricesStream Ciphers
Contact author(s)
gregory bard @ ieee org
History
2006-07-24: received
Short URL
https://ia.cr/2006/251
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.