Cryptology ePrint Archive: Report 2011/142

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

Haibo Yi and Shaohua Tang and 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.

Category / Keywords: implementation / Gaussian Elimination, Linear System of Equations (LSE), Forward Elimination, Field Programmable Gate Array (FPGA), Finite Field.

Date: received 22 Mar 2011, withdrawn 30 Jun 2011

Contact author: haibo yi87 at gmail com;shtang@IEEE org;huangege@qq com;sarlmolapple@gmail com;

Available format(s): (-- withdrawn --)

Version: 20110630:124913 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]