Efficient parallel evaluation of multivariate quadratic polynomials on GPUs

Satoshi Tanaka; Tung Chou; Bo Yin Yang; Chen Mou Cheng; Kouichi Sakurai

doi:10.1007/978-3-642-35416-8_3

Efficient parallel evaluation of multivariate quadratic polynomials on GPUs

Satoshi Tanaka, Tung Chou, Bo Yin Yang, Chen Mou Cheng, Kouichi Sakurai

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers
Editors	Dong Hoon Lee, Moti Yung
Publisher	Springer Verlag
Pages	28-42
Number of pages	15
ISBN (Print)	9783642354151
DOIs	https://doi.org/10.1007/978-3-642-35416-8_3
State	Published - 2012
Externally published	Yes
Event	13th International Workshop on Information Security Applications, WISA 2012 - Jeju Island, Korea, Republic of Duration: 16 08 2012 → 18 08 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7690 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Workshop on Information Security Applications, WISA 2012
Country/Territory	Korea, Republic of
City	Jeju Island
Period	16/08/12 → 18/08/12

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2012.

Keywords

Efficient implementation
GPGPU
Multivariate cryptography
Stream cipher

Access to Document

10.1007/978-3-642-35416-8_3

Cite this

Tanaka, S., Chou, T., Yang, B. Y., Cheng, C. M., & Sakurai, K. (2012). Efficient parallel evaluation of multivariate quadratic polynomials on GPUs. In D. H. Lee, & M. Yung (Eds.), Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers (pp. 28-42). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7690 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-35416-8_3

Tanaka, Satoshi ; Chou, Tung ; Yang, Bo Yin et al. / Efficient parallel evaluation of multivariate quadratic polynomials on GPUs. Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers. editor / Dong Hoon Lee ; Moti Yung. Springer Verlag, 2012. pp. 28-42 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1ba1b806f35b47b88eb13a1215d256d7,

title = "Efficient parallel evaluation of multivariate quadratic polynomials on GPUs",

abstract = "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.",

keywords = "Efficient implementation, GPGPU, Multivariate cryptography, Stream cipher",

author = "Satoshi Tanaka and Tung Chou and Yang, {Bo Yin} and Cheng, {Chen Mou} and Kouichi Sakurai",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2012.; 13th International Workshop on Information Security Applications, WISA 2012 ; Conference date: 16-08-2012 Through 18-08-2012",

year = "2012",

doi = "10.1007/978-3-642-35416-8_3",

language = "英语",

isbn = "9783642354151",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "28--42",

editor = "Lee, {Dong Hoon} and Moti Yung",

booktitle = "Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers",

address = "德国",

}

Tanaka, S, Chou, T, Yang, BY, Cheng, CM & Sakurai, K 2012, Efficient parallel evaluation of multivariate quadratic polynomials on GPUs. in DH Lee & M Yung (eds), Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7690 LNCS, Springer Verlag, pp. 28-42, 13th International Workshop on Information Security Applications, WISA 2012, Jeju Island, Korea, Republic of, 16/08/12. https://doi.org/10.1007/978-3-642-35416-8_3

Efficient parallel evaluation of multivariate quadratic polynomials on GPUs. / Tanaka, Satoshi; Chou, Tung; Yang, Bo Yin et al.
Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers. ed. / Dong Hoon Lee; Moti Yung. Springer Verlag, 2012. p. 28-42 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7690 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient parallel evaluation of multivariate quadratic polynomials on GPUs

AU - Tanaka, Satoshi

AU - Chou, Tung

AU - Yang, Bo Yin

AU - Cheng, Chen Mou

AU - Sakurai, Kouichi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2012.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Efficient implementation

KW - GPGPU

KW - Multivariate cryptography

KW - Stream cipher

UR - http://www.scopus.com/inward/record.url?scp=84906970691&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-35416-8_3

DO - 10.1007/978-3-642-35416-8_3

M3 - 会议稿件

AN - SCOPUS:84906970691

SN - 9783642354151

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 28

EP - 42

BT - Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers

A2 - Lee, Dong Hoon

A2 - Yung, Moti

PB - Springer Verlag

T2 - 13th International Workshop on Information Security Applications, WISA 2012

Y2 - 16 August 2012 through 18 August 2012

ER -

Tanaka S, Chou T, Yang BY, Cheng CM, Sakurai K. Efficient parallel evaluation of multivariate quadratic polynomials on GPUs. In Lee DH, Yung M, editors, Information Security Applications - 13th International Workshop, WISA 2012, Revised Selected Papers. Springer Verlag. 2012. p. 28-42. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-35416-8_3

Efficient parallel evaluation of multivariate quadratic polynomials on GPUs

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this