Achieving a log(n) Speed Up for Boolean Matrix Operations and Calculating the Complexity of the Dense Linear Algebra step of Algebraic Stream Cipher Attacks and of Integer Factorization Methods

Gregory V.  Bard

Paper 2006/163

Achieving a log(n) Speed Up for Boolean Matrix Operations and Calculating the Complexity of the Dense Linear Algebra step of Algebraic Stream Cipher Attacks and of Integer Factorization Methods

Gregory V. Bard

Abstract

The purpose of this paper is to calculate the running time of dense boolean matrix operations, as used in stream cipher cryptanalysis and integer factorization. Several variations of Gaussian Elimination, Strassen's Algorithm and the Method of Four Russians are analyzed. In particular, we demonstrate that Strassen's Algorithm is actually slower than the Four Russians algorithm for matrices of the sizes encountered in these problems. To accomplish this, we introduce a new model for tabulating the running time, tracking matrix reads and writes rather than field operations, and retaining the coefficients rather than dropping them. Furthermore, we introduce an algorithm known heretofore only orally, a ``Modified Method of Four Russians'', which has not appeared in the literature before. This algorithm is $\log n$ times faster than Gaussian Elimination for dense boolean matrices. Finally we list rough estimates for the running time of several recent stream cipher cryptanalysis attacks.

Note: More numerical testing will follow in updates to this paper.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Not yet published. Submitted to a conference.
Keywords: Matrix Inversion Matrix Multiplication Boolean Matrices GF(2)Stream Cipher Cryptanalysis XL Algorithm Strassen’s Algorithm Method of Four Russians Gaussian Elimination LU-factorization.
Contact author(s): gregory bard @ ieee org
History: 2006-05-16: received
Short URL: https://ia.cr/2006/163
License: CC BY

BibTeX

@misc{cryptoeprint:2006/163,
      author = {Gregory V.  Bard},
      title = {Achieving a log(n) Speed Up for Boolean Matrix Operations and Calculating the Complexity of the Dense Linear Algebra step of Algebraic Stream Cipher Attacks and of Integer Factorization Methods},
      howpublished = {Cryptology ePrint Archive, Paper 2006/163},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/163}},
      url = {https://eprint.iacr.org/2006/163}
}