Area-Efficient Subquadratic Space-Complexity Digit-Serial Multiplier for Type-II Optimal Normal Basis of $GF(2^{m})$ Using Symmetric TMVP and Block Recombination Techniques

The type-II optimal normal basis (ONB) is popularly used to represent GF(2^m) for elliptic curve cryptosystems. It is shown in the literature that multiplication in binary fields, including those represented by type-II ONB, shifted polynomial basis, and dual basis, can be transformed into non-symmetric Toeplitz matrix-vector product (TMVP) formulation. In this paper, we show that type-II ONB multiplication can be realized by two symmetric TMVPs (STMVP). Moreover, we have proposed a novel folded TMVP block recombination (TMVPBR) for the computation of STMVP. Based on the proposed folded TMVPBR approach, we have proposed a new digit-serial structure for type-II ONB multiplication, while traditional parallel ONB multipliers are based on non-symmetric TMVPBR approach to achieve subquadratic space complexity architecture. The proposed digit-serial structure also involves subquadratic space complexity. By the theoretical analysis as well as from synthesis result, however, we find that the proposed architecture has significantly less area and less area-delay product compared to the existing digit-serial type-II ONB multipliers.