Solving Polynomial Systems over Finite Fields: Improved Analysis of the Hybrid Approach

Luk Bettale 1 Jean-Charles Faugère 2, 3 Ludovic Perret 2, 3
3 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : The Polynomial System Solving (PoSSo) problem is a fundamental NP-Hard problem in computer algebra. Among others, PoSSo have applications in area such as coding theory and cryptology. Typically, the security of multivariate public-key schemes (MPKC) such as the UOV cryptosystem of Kipnis, Shamir and Patarin is directly related to the hardness of PoSSo over finite fields. The goal of this paper is to further understand the influence of finite fields on the hardness of PoSSo. To this end, we consider the so-called hybrid approach. This is a polynomial system solving method dedicated to finite fields proposed by Bettale, Faugère and Perret (Journal of Mathematical Cryptography, 2009). The idea is to combine exhaustive search with Gröbner bases. The efficiency of the hybrid approach is related to the choice of a trade-off between the two meth- ods. We propose here an improved complexity analysis dedicated to quadratic systems. Whilst the principle of the hybrid approach is simple, its careful analysis leads to rather surprising and somehow unexpected results. We prove that the optimal trade-off (i.e. num- ber of variables to be fixed) allowing to minimize the complexity is achieved by fixing a number of variables proportional to the number of variables of the system considered, denoted n. Under some nat- ural algebraic assumption, we show that the asymptotic complexity of the hybrid approach is 2^{n(3.31−3.62 log_2(q))} , where q is the size of the field (under the condition in particular that log(q) << n). This is to date, the best complexity for solving PoSSo over finite fields (when q > 2). We have been able to quantify the gain provided by the hybrid approach compared to a direct Gröbner basis method. For quadratic systems, we show (assuming a natural algebraic as- sumption) that this gain is exponential in the number of variables. Asymptotically, the gain is 2^{1.49 n} when both n and q grow to infinity and log(q) << n.
Type de document :
Communication dans un congrès
ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. ACM, pp.67--74, 2012, 〈10.1145/2442829.2442843〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00776070
Contributeur : Ludovic Perret <>
Soumis le : lundi 14 janvier 2013 - 23:55:14
Dernière modification le : jeudi 22 novembre 2018 - 14:09:24
Document(s) archivé(s) le : samedi 1 avril 2017 - 05:03:17

Fichier

MAYA2-UPMCINRIA-hybridext_1.0....
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Luk Bettale, Jean-Charles Faugère, Ludovic Perret. Solving Polynomial Systems over Finite Fields: Improved Analysis of the Hybrid Approach. ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. ACM, pp.67--74, 2012, 〈10.1145/2442829.2442843〉. 〈hal-00776070〉

Partager

Métriques

Consultations de la notice

478

Téléchargements de fichiers

775