Volume 4 - Issue 3
Fast Evaluation of Multivariate Quadratic Polynomials over GF(232) using Grahpics Processing Units
- Satoshi Tanaka
Kyushu University, Fukuoka, Japan, Institute of Systems, Information Technologies and Nanotechnologies, Fukuoka, Japan
tanasato@itslab.inf.kyushu-u.ac.jp
- Takanori Yasuda
Institute of Systems, Information Technologies and Nanotechnologies, Fukuoka, Japan
sakurai@csce.kyushu-u.ac.jp
- Kouichi Sakurai
Kyushu University, Fukuoka, Japan, Institute of Systems, Information Technologies and Nanotechnologies, Fukuoka, Japan
yasuda@isit.or.jp
Keywords: efficient implementation, multivariate public-key cryptography, GPU, QUAD, stream cipher
Abstract
QUAD stream cipher is a symmetric cipher based on multivariate public-key cryptography(MPKC),
which uses multivariate polynomials as encryption keys. It holds the provable security property based
on the computational hardness assumption. More specifically, the security of QUAD depends on the
hardness of solving non-linear multivariate quadratic systems over a finite field, which is known as
an NP-complete problem. However, QUAD is slower than other stream ciphers, and an efficient
implementation, which has a reduced computational cost, is required. In this paper, we propose
some implementations of QUAD over GF(232) on Graphics Processing Units(GPU) and compare
them. Moreover, we provide fast multiplications over GF(232), the core operation of QUAD. Our
implementation gives the fastest throughput of QUAD as 24.827 Mbps. We propose an efficient implementation
for computing with multivariate polynomials in multivariate cryptography on GPU and
evaluate the efficiency of the proposal. GPU is considered to be a commodity parallel arithmetic unit.
Our proposal parallelizes an algorithm coming from multivariate cryptography, and makes it efficient
by optimizing the algorithm with GPU.