Differential Cryptanalysis for Multivariate Schemes

Abstract : In this paper we propose a novel cryptanalytic method against multivariate schemes, which adapts differential cryptanalysis to this setting. In multivariate quadratic systems, the differential of the public key is a linear map and has invariants such as the dimension of the kernel. Using linear algebra, the study of this invariant can be used to gain information on the secret key. We successfully apply this new method to break the original Matsumoto-Imai cryptosystem using properties of the differential, thus providing an alternative attack against this scheme besides the attack devised by Patarin. Next, we present an attack against a randomised variant of the Matsumoto-Imai cryptosystem, called PMI. This scheme has recently been proposed by Ding, and according to the author, it resists all previously known attacks. We believe that differential cryptanalysis is a general and powerful method that can give additional insight on most multivariate schemes proposed so far.
Type de document :
Communication dans un congrès
Ronald Cramer. Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2005, Aarhus, Denmark. Springer, 3494, pp.341-353, 2005, Lecture Notes in Computer Science. 〈10.1007/11426639_20〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00563961
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 7 février 2011 - 16:28:57
Dernière modification le : mardi 24 avril 2018 - 17:20:13

Lien texte intégral

Identifiants

Collections

Citation

Pierre-Alain Fouque, Louis Granboulan, Jacques Stern. Differential Cryptanalysis for Multivariate Schemes. Ronald Cramer. Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2005, Aarhus, Denmark. Springer, 3494, pp.341-353, 2005, Lecture Notes in Computer Science. 〈10.1007/11426639_20〉. 〈inria-00563961〉

Partager

Métriques

Consultations de la notice

46