Cryptology ePrint Archive: Report 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).
Category / Keywords: secret-key cryptography / Algebraic Cryptanalysis, Factoring, Boolean Matrices, Stream Ciphers
Publication Info: Submitted to a Conference.
Date: received 22 Jul 2006
Contact author: gregory bard at ieee org
Available format(s): PDF | BibTeX Citation
Version: 20060724:100012 (All versions of this report)
Short URL: ia.cr/2006/251
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]