Fast exhaustive search for polynomial systems in F2
Ecole Normale Superieure, Paris, France
In Proceedings of the 12th international conference on Cryptographic hardware and embedded systems (2010), pp. 203-218.
@conference{bouillaguet2010fast,
title={Fast Exhaustive Search for Polynomial Systems in F2},
author={Bouillaguet, C. and Chen, H.C. and Cheng, C.M. and Chou, T. and Niederhagen, R. and Shamir, A. and Yang, B.Y.},
booktitle={Cryptographic Hardware and Embedded Systems, CHES 2010: 12th International Workshop, Santa Barbara, USA, August 17-20, 2010, Proceedings},
pages={203},
isbn={3642150306},
year={2010},
organization={Not Avail}
}
We analyze how fast we can solve general systems of multivariate equations of various low degrees over F2; 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.
March 9, 2011 by hgpu
