International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Accelerating Cryptanalysis with the Method of Four Russians

Authors:
Gregory V. Bard
Download:
URL: http://eprint.iacr.org/2006/251
Search ePrint
Search Google
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).
BibTeX
@misc{eprint-2006-21744,
  title={Accelerating Cryptanalysis with the Method of Four Russians},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Algebraic Cryptanalysis, Factoring, Boolean Matrices, Stream Ciphers},
  url={http://eprint.iacr.org/2006/251},
  note={Submitted to a Conference. gregory.bard@ieee.org 13351 received 22 Jul 2006},
  author={Gregory V. Bard},
  year=2006
}