SMITH - A Parallel Hardware Architecture for fast Gaussian Elimination over GF(2)0

Andrey Bogdanov, M. Mertens, Chris­tof Paar, Jan Pelzl, Andy Rupp

2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems - SHARCS 2006, Cologne, Germany, April 3-4, 2006.


This paper presents a hardware-optimized variant of the well-known Gaussian elimination over GF(2) and its highly ef?cient implementation. The proposed hardware architecture, we call SMITH 1 , 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 problemof matrix inversion extremely fast. Its average running time for nn binary matrices with uniformly distributed entries equals 2n (clock cycles) as opposed to about 1/4(n)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 ef?ciently solve medium-sized LSEs as they for example appear in the cryptanalysis of certain stream cipher classes.