Abstract:
This paper presents a hardware-optimized variant of the 
well-known Gaussian elimination over GF(2) and its highly 
efficient implementation. The proposed hardware architecture, 
we call SMITH, can solve any regular and (uniquely solvable) 
overdetermined linear system of equations (LSE) and is not 
limited to matrices of a certain structure. Besides solving 
LSEs, the architecture at hand can also accomplish the related 
problem of matrix inversion extremely fast. Its average 
running time for nxn binary matrices with uniformly distributed 
entries equals 2n (clock cycles) as opposed to about 1/4n^3 in 
software. The average running time remains very close to 2n
for random matrices with densities much greater or lower 
than 0.5. The architecture has a worst-case time complexity 
of O(n^2) and also a space complexity of O(n^2). With these 
characteristics the architecture is particularly suited to
efficiently solve medium-sized LSEs as they for example appear 
in the cryptanalysis of certain stream cipher classes.
Moreover, we propose a hardware-optimized algorithm for 
matrix-by-matrix multiplication over GF(2) which runs in linear 
time and quadratic space on a similar architecture. This opens 
up the possibility of building a more complex architecture for 
efficiently solving larger LSEs by means of Strassen's algorithm. 
This architecture could significantly improve the time complexity 
of algebraic attacks on various ciphers.

As proof-of-concept we realized SMITH on a contemporary low-cost 
FPGA. The implementation for a 50x50 LSE can be clocked with a 
frequency of up to 300 MHz and computes the solution in 
0.33 microseconds on average.


BibTeX:
@InProceedings{I-BMPPR06b,
  author =	 {A. Bogdanov and M. Mertens and C. Paar and J. Pelzl
                  and A. Rupp},
  title =	 "{SMITH - A Parallel Hardware Architecture for fast Gaussian
                  Elimination over GF(2)}",
  booktitle =	 "{International Workshop on Special-Purpose Hardware
                  for Attacking Cryptographic Systems --- SHARCS'06,
                  Cologne, Germany}",
  year =	 {2006},
  address =	 {\url{http://www.sharcs.org}},
  month =	 {April}
}