Name
Title | ||
|---|---|---|
Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications |
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]). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.vlsi.2010.09.001 | Integration |
Keywords | Field | DocType |
Cryptanalytic hardware,Cryptographic hardware,Linear equations,Gauss–Jordan elimination,SLE solver,SMITH,GSMITH,Systolic array | Linear equation,Computational problem,System of linear equations,Computer science,Cryptography,Field-programmable gate array,Systolic array,Stream cipher,Gaussian elimination,Computer hardware | Journal |
Volume | Issue | ISSN |
44 | 4 | 0167-9260 |
Citations | PageRank | References |
1 | 0.36 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andy Rupp | 1 | 196 | 16.95 |
| Thomas Eisenbarth | 2 | 840 | 61.33 |
| Andrey Bogdanov | 3 | 2067 | 98.10 |
| Oliver Grieb | 4 | 1 | 0.36 |