A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields

M. Hasan
University of Waterloo

The performance of some cryptosystems heavily relies on how fast arithmetic operations over finite fields can be performed. In this talk, a recently devised scheme for subquadratic space complexity parallel multipliers over binary fields will be presented. The scheme is based on Toeplitz matrix-vector products and coordinate transformation techniques. For a shifted polynomial basis, it is shown that both the space complexity and the asymptotic gate delay of the proposed multiplier are better than those of the well known Karatsuba algorithm based multipliers. Another advantage of the proposed matrix-vector product approach is that it can be used to design sub-quadratic space complexity polynomial, dual, weakly dual and triangular basis parallel multipliers. To the best of our knowledge, this is the first time that sub-quadratic space complexity parallel multipliers are proposed for dual, weakly dual and triangular bases.

Audio (MP3 File, Podcast Ready) Presentation (PDF File)

Back to Workshop IV: Special purpose hardware for cryptography: Attacks and Applications