Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications

Andy Rupp*, Thomas Eisenbarth, Andrey Bogdanov, Oliver Grieb

*Corresponding author for this work
3 Citations (Scopus)


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 F2k. 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]).

Original languageEnglish
JournalIntegration, the VLSI Journal
Issue number4
Pages (from-to)290-304
Number of pages15
Publication statusPublished - 01.09.2011


Dive into the research topics of 'Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications'. Together they form a unique fingerprint.

Cite this