Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications

Solving systems of linear equations (SLEs) is a very common computational problem appearing in numerous research disciplines and in particular in the context of cryptographic and cryptanalytic algorithms. In this work, we present highly efficient hardware architectures for solving (small and medium-sized) systems of linear equations over F2_k. These architectures feature linear or quadratic running times with quadratic space complexities in the size of an SLE, and can be clocked at high frequencies. Among the most promising architectures are one-dimensional and two-dimensional systolic arrays which we call triangular systolic and linear systolic arrays. All designs have been fully implemented for different sizes of SLEs and concrete FPGA implementation results are given. Furthermore, we provide a clear comparison of the presented SLE solvers. The significance of these designs is demonstrated by the fact that they are used in the recent literature as building blocks of efficient architectures for attacking block and stream ciphers (Bogdanov et al., 2007 [5]; Geiselmann et al., 2009 [17]) and for developing cores for multivariate signature schemes (Balasubramanian et al., 2008 [2]; Bogdanov et al., 2008 [6]).