Abstract
In this paper we propose a new multivariate public key encryption scheme named ZHFE. The public key is constructed using as core map two high rank HFE polynomials. The inversion of the public key is performed using a low degree polynomial of Hamming weight three. This low degree polynomial is obtained from the two high rank HFE polynomials, by means of a special reduction method that uses Hamming weight three polynomials produced from the two high rank HFE polynomials. We show that ZHFE is relatively efficient and that it is secure against the main attacks that have threatened the security of HFE. We also propose parameters for a practical implementation of ZHFE.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Ars, G., Faugère, J.-C., Imai, H., Kawazoe, M., Sugita, M.: Comparison Between XL and Gröbner Basis Algorithms. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 338–353. Springer, Heidelberg (2004)
Baena, J.B., Clough, C.L., Ding, J.: New Variants of the Square-Vinegar Signature Scheme, Revista Colombiana de Matemticas (Colombian Journal of Mathematics), Bogotá, 45(2) (2011)
Bernstein, D.J., Buchmann, J., Dahmen, E.: Post quantum cryptography. Springer (2009)
Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of hfe, multi-hfe and variants for odd and even characteristic. Designs, Codes and Cryptography 69(1), 1–52 (2013)
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24(3-4), 235–265 (1997); Computational algebra and number theory, London (1993)
Buss, J.F., Frandsen, G., Shallit, J.O.: The computational complexity of some problems of linear algebra. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 451–462. Springer, Heidelberg (1997)
Chen, C.H.O., Chen, M.S., Ding, J., Werner, F., Yang, B.Y.: Odd-char multivariate hidden field equations. cryptology eprint archive (2008)
Clough, C., Baena, J., Ding, J., Yang, B.-Y., Chen, M.-S.: Square, a New Multivariate Encryption Scheme. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 252–264. Springer, Heidelberg (2009)
Courtois, N.T.: The Security of Hidden Field Equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 266–281. Springer, Heidelberg (2001)
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Ding, J., Gower, J.E., Schmidt, D.S.: Zhuang-Zi: A New Algorithm for Solving Multivariate Polynomial Equations over a Finite Field, Preprint, University of Cincinnati (2006)
Ding, J., Gower, J.E., Schmidt, D.S.: Multivariate public key cryptosystems. Advances in Information Security, vol. 25. Springer, New York (2006)
Ding, J., Schmidt, D., Werner, F.: Algebraic Attack on HFE Revisited. In: Wu, T.-C., Lei, C.-L., Rijmen, V., Lee, D.-T. (eds.) ISC 2008. LNCS, vol. 5222, pp. 215–227. Springer, Heidelberg (2008)
Faugère, J.-C., Joux, A.: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)
Garey, M.R., Johnson, D.S., et al.: Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman, San Francisco (1979)
Jiang, X., Ding, J., Hu, L.: Kipnis-Shamir Attack on HFE Revisited. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds.) Inscrypt 2007. LNCS, vol. 4990, pp. 399–411. Springer, Heidelberg (2008)
Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999)
Patarin, J.: Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): Two new families of asymmetric algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Porras, J., Baena, J., Ding, J.: New candidates for multivariate trapdoor functions, Cryptology ePrint Archive, Report 2014/387 (2014), http://eprint.iacr.org/2014/387.pdf
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. on Computing, 1484–1509 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Porras, J., Baena, J., Ding, J. (2014). ZHFE, a New Multivariate Public Key Encryption Scheme. In: Mosca, M. (eds) Post-Quantum Cryptography. PQCrypto 2014. Lecture Notes in Computer Science, vol 8772. Springer, Cham. https://doi.org/10.1007/978-3-319-11659-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-11659-4_14
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11658-7
Online ISBN: 978-3-319-11659-4
eBook Packages: Computer ScienceComputer Science (R0)