Key Recovery on Hidden Monomial Multivariate Schemes

Abstract : The problem we study in this paper is the key recovery problem on the C* schemes and generalizations where the quadratic monomial of C* (the product of two linear monomials) is replaced by a product of three or more linear monomials. This problem has been further generalized to any multivariate polynomial hidden by two invertible linear maps and named the Isomorphism of Polynomials (I P ) problem by Patarin et al. Some cryptosystems have been built on this appearing hard problem such as a traitor tracing scheme proposed by Billet and Gilbert. Here we show that if the hidden multivariate monomial is a quadratic monomial, as in SFLASH, or a cubic (or higher) monomial as in the traitor tracing scheme, then it is possible to recover an equivalent secret key in polynomial time O(nd ) where n is the number of variables and d is the degree of the public polynomials.
Type de document :
Communication dans un congrès
Nigel P. Smart. Advances in Cryptology - EUROCRYPT 2008 : 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2008, Istanbul, Turkey. Springer, 4965, pp.19-30, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-78967-3_2〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00556685
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 17 janvier 2011 - 15:37:56
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 6 novembre 2012 - 11:37:43

Fichier

euro08a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre-Alain Fouque, Gilles Macario-Rat, Jacques Stern. Key Recovery on Hidden Monomial Multivariate Schemes. Nigel P. Smart. Advances in Cryptology - EUROCRYPT 2008 : 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2008, Istanbul, Turkey. Springer, 4965, pp.19-30, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-78967-3_2〉. 〈inria-00556685〉

Partager

Métriques

Consultations de la notice

265

Téléchargements de fichiers

136