Nuevas candidatas para funciones trampa multivariadas

New Candidates for Multivariate Trapdoor Functions

Presentamos un nuevo método de reducción que permite construir
parejas de polinomios HFE de grado alto, tal que la función construida con
cada una de estas parejas de polinomios es fácil de invertir. Para invertir la
pareja de polinomios usamos un polinomio de grado bajo y de peso de Ham-
ming tres, el cual es derivado mediante un método especial de reducción que
involucra polinomios de peso de Hamming tres producidos a partir de los dos
polinomios HFE. Esto nos permite construir nuevas candidatas para funciones
trampa multivariadas usando la pareja de polinomios HFE para construir la
función central. Realizamos un análisis de seguridad cuando el campo base es
GF(2) y mostramos que estas nuevas funciones trampa multivariadas tienen grado de regularidad alto,
y por lo tanto resisten el ataque algebraico. Además
damos argumentos teóricos para mostrar que estas nuevas funciones trampa
sobre GF(2) tambien resisten el ataque MinRank.

We present a new method for building pairs of HFE polynomials
of high degree, such that the map constructed with one of these pairs is easy
to invert. The inversion is accomplished using a low degree polynomial of
Hamming weight three, which is derived from a special reduction via Hamming
weight three polynomials produced by these two HFE polynomials. This allows
us to build new candidates for multivariate trapdoor functions in which we
use the pair of HFE polynomials to fabricate the core map. We performed the
security analysis for the case where the base eld is GF(2) and showed that
these new trapdoor functions have high degrees of regularity, and therefore
they are secure against the direct algebraic attack. We also give theoretical
arguments to show that these new trapdoor functions over GF(2) are secure
against the MinRank attack as well.

New Candidates for Multivariate Trapdoor Functions Nuevas candidatas para funciones trampa multivariadas JAIBERTH PORRAS¹, JOHN B. BAENA², JINTAI DING³

¹Universidad Nacional de Colombia, Medellín, Colombia. Email: jporras@unal.edu.co
²Universidad Nacional de Colombia, Medellín, Colombia. Email: jbbaena@unal.edu.co
³University of Cincinnati, Cincinnati, OH, USA. Email: jintai.ding@uc.edu

---

Abstract

We present a new method for building pairs of HFE polynomials of high degree, such that the map constructed with one of these pairs is easy to invert. The inversion is accomplished using a low degree polynomial of Hamming weight three, which is derived from a special reduction via Hamming weight three polynomials produced by these two HFE polynomials. This allows us to build new candidates for multivariate trapdoor functions in which we use the pair of HFE polynomials to fabricate the core map. We performed the security analysis for the case where the base field is GF(2) and showed that these new trapdoor functions have high degrees of regularity, and therefore they are secure against the direct algebraic attack. We also give theoretical arguments to show that these new trapdoor functions over GF(2) are secure against the MinRank attack as well.

Key words: Multivariate cryptography, HFE polynomials, HFE cryptosystem, Trapdoor functions, Zhuang-zi algorithm.

---

2000 Mathematics Subject Classification: 11T71, 11Y40.

---

Resumen

Presentamos un nuevo método de reducción que permite construir parejas de polinomios HFE de grado alto, tal que la función construida con cada una de estas parejas de polinomios es fácil de invertir. Para invertir la pareja de polinomios usamos un polinomio de grado bajo y de peso de Hamming tres, el cual es derivado mediante un método especial de reducción que involucra polinomios de peso de Hamming tres producidos a partir de los dos polinomios HFE. Esto nos permite construir nuevas candidatas para funciones trampa multivariadas usando la pareja de polinomios HFE para construir la función central. Realizamos un análisis de seguridad cuando el campo base es GF(2) y mostramos que estas nuevas funciones trampa multivariadas tienen grado de regularidad alto, y por lo tanto resisten el ataque algebraico. Además damos argumentos teóricos para mostrar que estas nuevas funciones trampa sobre GF(2) también resisten el ataque MinRank.

Palabras clave: Criptografía multivariada, polinomios HFE, criptosistema HFE, funciones trampa, algoritmo Zhuang-zi.

---

Texto completo disponible en PDF

---

References

[1] D. J. Bernstein, J. Buchmann, and E. Dahmen, Post Quantum Cryptography, Springer, 2009.

[2] L. Bettale, Jean-Charles Faugère, and L. Perret, `Cryptanalysis of HFE, Multi-HFE and Variants for odd and even Characteristic´, Designs, Codes and Cryptography 69, 1 (2013), 1-52.

[3] W. Bosma, J. Cannon, and C. Playoust, `The Magma Algebra System. I. The User Language´, J. Symbolic Comput. 24, 3--4 (1997), 235-265. Computational algebra and number theory (London, 1993)

[4] Chia-Hsin Owen Chen, Ming-Shing Chen, J. Ding, F. Werner, and Bo-Yin Yang, Odd-char multivariate hidden field equations, `IACR Eprint archive´, (2008).

[5] C. Clough, J. Baena, J. Ding, Bo-Yin Yang, and Ming-shing Chen, Square, a New Multivariate Encryption Scheme, `CT-RSA 2009´, (2009), Springer, Berlin, Germany.

[6] N. Courtois, A. Klimov, J. Patarin, and A. Shamir, Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations, `Advances in Cryptology-EUROCRYPT 2000´, 2000, Vol. 1807 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, p. 392-407.

[7] J. Ding, J. Buchmann, M. Mohamed, W. Mohamed, and R. Weinmann, Mutant xl, `First International Conference on Symbolic Computation and Cryptography (SCC 2008)´, (2008), Beijing, China.

[8] J. Ding, J. E. Gower, and D. S. Schmidt, Multivariate Public Key Cryptosystems, Vol. 25 of Advances in Information Security, Springer, New York, USA, 2006.

[9] J. Ding and T. J. Hodges, Inverting HFE Systems is Quasi-Polynomial for All Fields, `Advances in Cryptology-CRYPTO 2011´, (2011), Vol. 6841 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, p. 724-742.

[10] J. Ding and D. Schmidt, Cryptanalysis of HFEv and Internal Perturbation of HFE, `Public key cryptography-PKC 2005´, (2005), Vol. 3386 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 288-301.

[11] Jean-Charles Faugère and A. Joux, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases, `Advances in cryptology-CRYPTO 2003´, (2003), Vol. 2729 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 44-60.

[12] A. Kipnis, J. Patarin, and L. Goubin, Unbalanced Oil and Vinegar Signature Schemes, `Advances in cryptology-EUROCRYPT '99 (Prague)´, (1999), Vol. 1592 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 206-222.

[13] A. Kipnis and A. Shamir, Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization, `Advances in cryptology-CRYPTO '99 (Santa Barbara, CA)´, (1999), Vol. 1666 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 19-30.

[14] M. S. E. Mohamed, D. Cabarcas, J. Ding, J. Buchmann, and S. Bulygin, MXL3: An Efficient Algorithm for Computing Gröbner Bases of Zero-Dimensional Ideals, `Information, Security and Cryptology ? ICISC 2009´, (2010), Vol. 5984 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, p. 87-100.

[15] M. S. E. Mohamed, W. S. A. E. Mohamed, J. Ding, and J. Buchmann, MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy, `Post-Quantum Cryptography´, (2008), Vol. 5299 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, p. 203-215.

[16] J. Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, `Advances in Cryptology ? EUROCRYPT ?96´, (1996), Vol. 1070 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, p. 33-48.

[17] P. W. Shor, `Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer´, SIAM J. on Computing, (1997), 1484-1509.

---

(Recibido en febrero de 2014. Aceptado en noviembre de 2014)

---

Este artículo se puede citar en LaTeX utilizando la siguiente referencia bibliográfica de BibTeX:

@ARTICLE{RCMv49n1a03,
    AUTHOR  = {Porras, Jaiberth and Baena, John B. and Ding, Jintai},
    TITLE   = {{New Candidates for Multivariate Trapdoor Functions}},
    JOURNAL = {Revista Colombiana de Matemáticas},
    YEAR    = {2015},
    volume  = {49},
    number  = {1},
    pages   = {57--76}
}

---