The Taub Faculty of Computer Science Events and Talks
Thursday, 31.05.2007, 14:30
The security of the RSA cryptosystem is based on the difficulty of
solving a single algebraic equation in one variable over a large domain. The
security of multivariate cryptosystems is based on the difficulty of
solving many algebraic equations in many variables over a small domain. The best
known such scheme is SFLASH, which is basically an obfuscated variant of
RSA with many variables. It was selected in 2003 by the European NESSIE
project as one of only three recommended signature schemes, and as the one most
suitable for constrained devices. In this talk I will describe a new
cryptanalytic technique which can break SFLASH with its largest
recommended parameters in a few seconds on a single PC.
This is a very recent joint work with Dubois, Fouque, and Stern. The talk
will be self contained, requiring only basic knowledge about the structure
of finite fields.