Paper 2010/313

Fast Exhaustive Search for Polynomial Systems in $F_2$

Charles Bouillaguet, Chen-Mou Cheng, Tony (Tung) Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang

Abstract

We analyze how fast we can solve general systems of multivariate equations of various low degrees over \GF{2}; 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. Modern graphic cards allows our technique to run more than 10 times faster than the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a NVIDIA GTX 295 video card (USD 500) 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 power of GPUs in solving many types of combinatorial and cryptanalytic problems.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Will be an extended version of our paper at CHES 2010
Keywords
multivariate polynomialssystem-solvingparallelizationGraphic Processing Units (GPUs)
Contact author(s)
by @ crypto tw
History
2010-05-26: revised
2010-05-25: received
See all versions
Short URL
https://ia.cr/2010/313
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/313,
      author = {Charles Bouillaguet and Chen-Mou Cheng and Tony (Tung) Chou and Ruben Niederhagen and Adi Shamir and Bo-Yin Yang},
      title = {Fast Exhaustive Search for Polynomial Systems in $F_2$},
      howpublished = {Cryptology ePrint Archive, Paper 2010/313},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/313}},
      url = {https://eprint.iacr.org/2010/313}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.