On enumeration of polynomial equivalence classes and their application to MPKC

Abstract : The Isomorphism of Polynomials (IP) is one of the most fundamental problems in multivariate public key cryptography (MPKC). In this paper, we introduce a new framework to study the counting problem associated to IP. Namely, we present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, we focus on enumerating or estimating the number of isomorphism equivalence classes of homogeneous quadratic polynomial systems. These problems are equivalent to finding the scale of the key space of a multivariate cryptosystem and the total number of different multivariate cryptographic schemes respectively, which might impact the security and the potential capability of MPKC. We also consider their applications in the analysis of a specific multivariate public key cryptosystem. Our results not only answer how many cryptographic schemes can be derived from monomials and how big the key space is for a fixed scheme, but also show that quite many HFE cryptosystems are equivalent to a Matsumoto-Imai scheme.
Type de document :
Article dans une revue
Finite Fields and Their Applications, Elsevier, 2012, 18 (2), pp.283-302. 〈http://www.sciencedirect.com/science/article/pii/S1071579711000797〉. 〈10.1016/j.ffa.2011.09.001〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00776073
Contributeur : Ludovic Perret <>
Soumis le : mardi 15 janvier 2013 - 15:30:08
Dernière modification le : vendredi 3 novembre 2017 - 22:24:06
Document(s) archivé(s) le : mardi 16 avril 2013 - 03:52:42

Fichier

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

Identifiants

Collections

Citation

Dongdai Lin, Jean-Charles Faugère, Ludovic Perret, Tianze Wang. On enumeration of polynomial equivalence classes and their application to MPKC. Finite Fields and Their Applications, Elsevier, 2012, 18 (2), pp.283-302. 〈http://www.sciencedirect.com/science/article/pii/S1071579711000797〉. 〈10.1016/j.ffa.2011.09.001〉. 〈hal-00776073〉

Partager

Métriques

Consultations de la notice

208

Téléchargements de fichiers

116