A method for flexible reduction over binary fields using a field multiplier

Flexibility in implementation of the underlying field algebra kernels often dictates the life-span of an Elliptic Curve Cryptography solution. The systems/methods designed to realize binary field arithmetic operations can be tuned either for performance or for flexibility. Usually flexibility of these solutions adversely affects their performance. For solutions to reduction operation this adverse effect is particularly prominent. Therefore it is a non-trivial task to design a flexible reduction method/system without compromising performance. In this paper we present a method for flexible reduction. The proposed reduction technique is based on the well-known repeated multiplication technique and Barrett reduction. This technique is particularly appealing in the context of coarse-grain programmable architectures where performance of any kernel is heavily influenced by granularity of operations. In this context we propose a design of a polynomial multiplier based on the well-known Interleaved Galois Field multiplier to accelerate the underlying multi-word polynomial multiplications. We show that this modified IGF multiplier offers a significant improvement in throughput over a purely software realization or a hybrid software-hardware implementation using a conventional polynomial multiplier.