Efficient Parallel Evaluation of Multivariate Quadratic Polynomials on GPUs

Satoshi Tanaka, Tung Chou, Bo-Yin Yang, Chen-Mou Cheng, Kouichi Sakurai
Kyushu University, Fukuoka, Japan
The 13th International Workshop on Information Security Applications (WISA2012), 2012


   title={Efficient Parallel Evaluation of Multivariate Quadratic Polynomials on GPUs},

   author={Tanaka, S. and Chou, T. and Yang, B.Y. and Cheng, C.M. and Sakurai, K.},



Download Download (PDF)   View View   Source Source   



QUAD is a provably secure stream cipher, whose security is based on the hardness assumption of solving multivariate quadratic polynomial systems over a finite field, which is known to be NP-complete. However, such provable security comes at a price, and QUAD is slower than most other stream ciphers that do not have security proofs. In this paper, we discuss two efficient parallelization techniques for evaluating multivariate quadratic polynomial systems on GPU, which can effectively accelerate the QUAD stream cipher. The first approach focuses on formula of summations in quadratics, while the second approach uses parallel reduction to summations. Our approaches can be easily generalized and applied to other multivariate cryptosystems.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: