CWI Cryptology Group

Abstract: 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 joint work with Dubois, Fouque, and Stern. The talk will be self contained, requiring only basic knowledge about the structure of finite fields.