Fast Evaluation of Multivariate Quadratic Polynomials over GF(2³²) using Grahpics Processing Units

Satoshi Tanaka^{1, 2+}, Takanori Yasuda², and Kouichi Sakurai^{1, 2}

¹Kyushu University, Fukuoka, Japan
tanasato@itslab.inf.kyushu-u.ac.jp, sakurai@csce.kyushu-u.ac.jp

²Institute of Systems, Information Technologies and Nanotechnologies, Fukuoka, Japan

yasuda@isit.or.jp

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(2³²) on Graphics Processing Units(GPU) and compare them. Moreover, we provide fast multiplications over GF(2³²), 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.

Keywords: efficient implementation, multivariate public-key cryptography, GPU, QUAD, stream cipher

+: Corresponding author: Satoshi Tanaka
Room 712, West 2 building, 744 Motooka, Nishi-ku, Fukuoka, Fukuoka 819 -0395, Japan,
Tel: +81-928023639

Journal of Internet Services and Information Security (JISIS), 4(3): 1-20, August 2014 [pdf]