Fast exhaustive search for polynomial systems in F2

Charles Bouillaguet; Hsieh Chung Chen; Chen Mou Cheng; Tung Chou; Ruben Niederhagen; Adi Shamir; Bo Yin Yang

doi:10.1007/978-3-642-15031-9_14

Fast exhaustive search for polynomial systems in F₂

Charles Bouillaguet^*, Hsieh Chung Chen, Chen Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, Bo Yin Yang

^*Corresponding author for this work

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

51 Scopus citations

Abstract

We analyze how fast we can solve general systems of multivariate equations of various low degrees over ; this is a well known hard problem which is important both in itself and as part of many types of algebraic cryptanalysis. Compared to the standard exhaustive search technique, our improved approach is more efficient both asymptotically and practically. We implemented several optimized versions of our techniques on CPUs and GPUs. Our technique runs more than 10 times faster on modern graphic cards than on the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a 500-dollar NVIDIA GTX 295 graphics card in 21 minutes. With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the computational power of GPUs in solving many types of combinatorial and cryptanalytic problems.

Original language	English
Title of host publication	Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings
Publisher	Springer Verlag
Pages	203-218
Number of pages	16
ISBN (Print)	3642150306, 9783642150302
DOIs	https://doi.org/10.1007/978-3-642-15031-9_14
State	Published - 2010
Externally published	Yes
Event	12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010 - Santa Barbara, CA, United States Duration: 17 08 2010 → 20 08 2010

Publication series

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

Conference

Conference	12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010
Country/Territory	United States
City	Santa Barbara, CA
Period	17/08/10 → 20/08/10

Keywords

Exhaustive search
Graphic Processing Units (GPUs)
Multivariate polynomials
Parallelization
Solving systems of equations

Access to Document

10.1007/978-3-642-15031-9_14

Cite this

Bouillaguet, C., Chen, H. C., Cheng, C. M., Chou, T., Niederhagen, R., Shamir, A., & Yang, B. Y. (2010). Fast exhaustive search for polynomial systems in F₂. In Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings (pp. 203-218). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6225 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-15031-9_14

Bouillaguet, Charles ; Chen, Hsieh Chung ; Cheng, Chen Mou et al. / Fast exhaustive search for polynomial systems in F₂. Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings. Springer Verlag, 2010. pp. 203-218 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{369798da7fca43bbad6082aa9bb2426a,

title = "Fast exhaustive search for polynomial systems in F2",

abstract = "We analyze how fast we can solve general systems of multivariate equations of various low degrees over ; this is a well known hard problem which is important both in itself and as part of many types of algebraic cryptanalysis. Compared to the standard exhaustive search technique, our improved approach is more efficient both asymptotically and practically. We implemented several optimized versions of our techniques on CPUs and GPUs. Our technique runs more than 10 times faster on modern graphic cards than on the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a 500-dollar NVIDIA GTX 295 graphics card in 21 minutes. With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the computational power of GPUs in solving many types of combinatorial and cryptanalytic problems.",

keywords = "Exhaustive search, Graphic Processing Units (GPUs), Multivariate polynomials, Parallelization, Solving systems of equations",

author = "Charles Bouillaguet and Chen, {Hsieh Chung} and Cheng, {Chen Mou} and Tung Chou and Ruben Niederhagen and Adi Shamir and Yang, {Bo Yin}",

year = "2010",

doi = "10.1007/978-3-642-15031-9_14",

language = "英语",

isbn = "3642150306",

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

publisher = "Springer Verlag",

pages = "203--218",

booktitle = "Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings",

address = "德国",

note = "12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010 ; Conference date: 17-08-2010 Through 20-08-2010",

}

Bouillaguet, C, Chen, HC, Cheng, CM, Chou, T, Niederhagen, R, Shamir, A & Yang, BY 2010, Fast exhaustive search for polynomial systems in F₂. in Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6225 LNCS, Springer Verlag, pp. 203-218, 12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010, Santa Barbara, CA, United States, 17/08/10. https://doi.org/10.1007/978-3-642-15031-9_14

Fast exhaustive search for polynomial systems in F₂. / Bouillaguet, Charles; Chen, Hsieh Chung; Cheng, Chen Mou et al.
Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings. Springer Verlag, 2010. p. 203-218 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6225 LNCS).

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

TY - GEN

T1 - Fast exhaustive search for polynomial systems in F2

AU - Bouillaguet, Charles

AU - Chen, Hsieh Chung

AU - Cheng, Chen Mou

AU - Chou, Tung

AU - Niederhagen, Ruben

AU - Shamir, Adi

AU - Yang, Bo Yin

PY - 2010

Y1 - 2010

N2 - We analyze how fast we can solve general systems of multivariate equations of various low degrees over ; this is a well known hard problem which is important both in itself and as part of many types of algebraic cryptanalysis. Compared to the standard exhaustive search technique, our improved approach is more efficient both asymptotically and practically. We implemented several optimized versions of our techniques on CPUs and GPUs. Our technique runs more than 10 times faster on modern graphic cards than on the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a 500-dollar NVIDIA GTX 295 graphics card in 21 minutes. With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the computational power of GPUs in solving many types of combinatorial and cryptanalytic problems.

AB - We analyze how fast we can solve general systems of multivariate equations of various low degrees over ; this is a well known hard problem which is important both in itself and as part of many types of algebraic cryptanalysis. Compared to the standard exhaustive search technique, our improved approach is more efficient both asymptotically and practically. We implemented several optimized versions of our techniques on CPUs and GPUs. Our technique runs more than 10 times faster on modern graphic cards than on the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a 500-dollar NVIDIA GTX 295 graphics card in 21 minutes. With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the computational power of GPUs in solving many types of combinatorial and cryptanalytic problems.

KW - Exhaustive search

KW - Graphic Processing Units (GPUs)

KW - Multivariate polynomials

KW - Parallelization

KW - Solving systems of equations

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

U2 - 10.1007/978-3-642-15031-9_14

DO - 10.1007/978-3-642-15031-9_14

M3 - 会议稿件

AN - SCOPUS:78049336783

SN - 3642150306

SN - 9783642150302

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

SP - 203

EP - 218

BT - Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings

PB - Springer Verlag

T2 - 12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010

Y2 - 17 August 2010 through 20 August 2010

ER -

Bouillaguet C, Chen HC, Cheng CM, Chou T, Niederhagen R, Shamir A et al. Fast exhaustive search for polynomial systems in F₂. In Cryptographic Hardware and Embedded Systems, CHES 2010 - 12th International Workshop, Proceedings. Springer Verlag. 2010. p. 203-218. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-15031-9_14