Solving large systems of linear equations over GF(2) on FPGAs
Authors:
- 16 February 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
Abstract
This paper presents an efficient systolic line architecture for solving large systems of linear equations using Gaussian elimination on the coefficient matrix. Our architecture can also be used for solving matrix inversion problems and for computing the systematic form of matrices. These are common and important computational problems that appear in areas such as cryptography and cryptanalysis. Our architecture solves these problems efficiently for any large-sized matrix over GF(2), regardless of matrix size, shape or density. We implemented and synthesized our design for Altera and Xilinx FPGAs to obtain evaluation data. The results show sub-μs performance for the Gaussian elimination of medium-sized matrices and performance on the order of tens to hundreds of ms for large matrices. In addition, this is one of the first works addressing large-sized matrices of up to 4,000 × 8,000 elements and therefore is suitable for post-quantum cryptographic schemes that require handling such large matrices.Keywords
This publication has 5 references indexed in Scilit:
- Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplicationsIntegration, 2011
- An Improved GF(2) Matrix Inverter with Linear Time Complexity2010
- A Novel Cryptoprocessor Architecture for the McEliece Public-Key CryptosystemIEEE Transactions on Computers, 2010
- A systolic architecture for computing inverses and divisions in finite fields GF(2/sup m/)IEEE Transactions on Computers, 1993
- Systolic Gaussian elimination over GF(p) with partial pivotingIEEE Transactions on Computers, 1989