Hybrid Approach : a Tool for Multivariate Cryptography
| Autor: | Bettale, Luk, Faugère, Jean-Charles, Perret, Ludovic |
|---|---|
| Přispěvatelé: | Solvers for Algebraic Systems and Applications (SALSA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | Tools'10: Proceedings of the Workshop on Tools for Cryptanalysis 2010 Tools'10: the Workshop on Tools for Cryptanalysis 2010 Tools'10: the Workshop on Tools for Cryptanalysis 2010, Jun 2010, London, United Kingdom. pp.15-23 |
| Popis: | International audience; In this paper, we present an algorithmic tool to cryptanalysis multivariate cryptosystems. The presented algorithm is a hybrid approach that mixes exhaustive search with classical Gröbner bases computation to solve multivariate polynomial systems over a finite field. Depending on the size of the field, our method is an improvement on existing techniques. For usual parameters of multivariate schemes, our method is effective. We give theoretical evidences on the efficiency of our approach as well as practical cryptanalysis of several multivariate signature schemes (TRMS, UOV) that were considered to be secure. For instance, on TRMS, our approach allow to forge a valid signature in 267 operations instead of 2160 with exhaustive search or 283 with only Gröbner bases. Our algorithm is general as its efficiency is demonstrated on random systems of equations. As the structure of the cryptosystem is not involved, our algorithm provides a generic tool to calibrate the parameters of any multivariate scheme. These results were already published in [5]. We also present an extended version of our hybrid approach, suitable for polynomials of higher degree. To easily access our tools, we provide a MAGMA package available at http://www-salsa.lip6.fr/ ̃bettale/hybrid.html that provide all the necessary material to use our hybrid approach and to compute the complexities. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|