Subquadratic Complexity Gaussian Normal Basis Multiplier over GF(2^m) Using Addition of HMVP and TMVP

Abstract

Efficient and high-performance ECC system plays an important role in network security. We propose a subquadratic complexity digit-serial multiplier based on Gaussian normal basis (GNB) employing Palindromic polynomial decomposition. Using Palindromic polynomial representation, GNB multiplication is expressed as the sum of a Hankel matrix-vector product (HMVP) and a Toeplitz matrix-vector product (TMVP). We present the novel addition of HMVP and TMVP scheme with subquadratic complexities applying two-way TMVP approach. Combining with Palindromic polynomial decomposition and partial product, GNB multiplication is implemented by a digit-serial architecture. According to the theoretical analysis, the proposed digit-serial multiplier has a lower complexities and a better trade-off between time and area.