Tutte seminar - David Jao

Algorithms for Gaussian Normal Basis Multipliers

Abstract:

We propose new algorithms for reducing the space complexity of Gaussian normal basis (GNB) multipliers over binary fields of odd extension degree. Compared to previous results, our approach incurs no additional costs in time complexity, and achieves improvements in space complexity over a wide range of finite fields and digit sizes. For example, over the binary fields specified in the NIST FIPS 186-3 ECDSA standard, our algorithms reduce by 16 percent (respectively, 27 percent) the number of XOR gates needed for the implementation of a digit-level parallel-input parallel-output multiplier over a 163-bit (respectively, 409-bit) binary field.

Joint work with Reza Azarderakhsh and Hao Lee