Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications

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

*Korrespondierende/r Autor/-in für diese Arbeit
3 Zitate (Scopus)

Abstract

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

OriginalspracheEnglisch
ZeitschriftIntegration, the VLSI Journal
Jahrgang44
Ausgabenummer4
Seiten (von - bis)290-304
Seitenumfang15
ISSN0167-9260
DOIs
PublikationsstatusVeröffentlicht - 01.09.2011

Fingerprint

Untersuchen Sie die Forschungsthemen von „Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren