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.
Category / Keywords: implementation / multivariate polynomials, system-solving, parallelization, Graphic Processing Units (GPUs) Publication Info: Will be an extended version of our paper at CHES 2010 Date: received 25 May 2010, last revised 26 May 2010 Contact author: by at crypto tw Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20100526:082531 (All versions of this report) Short URL: ia.cr/2010/313 Discussion forum: Show discussion | Start new discussion