Efficient Implementation of Multiplication on Extension Field Using GPU

Evaluating non-linear multivariate polynomial systems over finite fields is an important subroutine for encryption and signature verification in multivariate public-key cryptography (MPKC). The security of MPKC definitely becomes lower if a larger field is used instead of ?F(2) given the same number of bits in the key. However, we still would like to use larger fields because MPKC tends to run faster at the same level of security if a larger field is used. The heaviest computation of evaluating non-linear multivariate polynomial system is multiplication. Therefore, we must find the best way of multiplications. Nowadays, graphics processing units (GPUs) have over 100 times computational power than CPU. They are constructed by hundreds cores. Hence, it seems that GPUs are suited as parallel general computing machines. Therefore, researchers applied parallel algorithms to GPUs. In this work, we compare the efficiency of several techniques for multiplication methods over ?F(2^<16>) via their implementations on a CPU and a GPU. In CPU implementations, Zech\u27s method is fastest, and it multiplies 67,108,864 instances in 1.2 seconds. On the other hand, for GPU implementations, it seems that ?F(2^4) is a very efficient intermediary field for building extension fields over ?F(2^<16>) . The time of 67,108,864 multiplications is about 60.3 milliseconds. GPU implementations are about 20 times faster than CPU implementations