Paper 2011/142

A Parallel Hardware Architecture for the Solution of Linear Equation Systems Implemented over GF(2^n)

Haibo Yi, Shaohua Tang, Huan Chen, and Guomin Chen

Abstract

A parallel hardware architecture for the solution of linear equation systems implemented over finite fields is presented in this paper. This proposed hardware architecture could be efficiently employed in the Multivariate Public Key Cryptosystems for hardware implementation. A hardware-paralleled variant of the Gaussian elimination is adopted and is expressed as a series of multiplications with three inputs over finite fields, where the basic common computations can be shared to reduce computational complexity. Its average running time for solving a linear system Ax=b equals n clock cycles, where A is a n*n matrix with uniformly distributed entries. In other words, it reduces time complexity to O(n). Besides, its worst-case time is equal to its best-case one. The proposed architecture is implemented on a Field Programmable Gate Array. This implementation for solving a 12*12 linear system can be clocked with a frequency of up to 50 MHz and computed in 0.24 us.

Metadata
Available format(s)
-- withdrawn --
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Gaussian EliminationLinear System of Equations (LSE)Forward EliminationField Programmable Gate Array (FPGA)Finite Field.
Contact author(s)
haibo yi87 @ gmail com
shtang @ ieee org
huangege @ qq com
sarlmolapple @ gmail com
History
2011-06-30: withdrawn
2011-03-27: received
See all versions
Short URL
https://ia.cr/2011/142
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.