×

On enumeration of polynomial equivalence classes and their application to MPKC. (English) Zbl 1251.94033

Summary: 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.

MSC:

94A60 Cryptography
05B25 Combinatorial aspects of finite geometries
11T55 Arithmetic theory of polynomial rings over finite fields
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry

Software:

FGb
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Matsumoto, Tsutomu; Imai, Hideki, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, (Advances in Cryptology - EUROCRYPT 1988. Advances in Cryptology - EUROCRYPT 1988, Lecture Notes in Comput. Sci., vol. 330 (1988), Springer-Verlag), 419-453 · Zbl 0655.94013
[2] Jacques Patarin, The Oil and Vinegar signature scheme, presented at the Dagstuhl Workshop on Cryptography, 1997.; Jacques Patarin, The Oil and Vinegar signature scheme, presented at the Dagstuhl Workshop on Cryptography, 1997.
[3] Patarin, Jacques; Goubin, Louis; Courtois, Nicolas, \(C^{⁎−+}\) and hm: Variations around two schemes of t.matsumoto and h.imai, (Advances in Cryptology - Asiacrypt ʼ98, vol. 1514 (1998), Springer), 35-49 · Zbl 1036.94534
[4] Patarin, Jacques; Courtois, Nicolas; Goubin, Louis, Quartz, 128-bit long digital signatures, (CT-RSA ʼ01, vol. 2020 (2001), Springer), 282-297 · Zbl 0972.68074
[5] Wolf, Christopher; Preneel, Bart, Taxonomy of public key schemes based on the problem of multivariate quadratic equations (2005), Cryptology ePrint Archive, Report 2005/077 · Zbl 1081.94541
[6] Shor, Peter W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509 (1997) · Zbl 1005.11065
[7] Wolf, Christopher; Preneel, Bart, Large superfluous keys in multivariate quadratic asymmetric systems, (Public Key Cryptography (2005)), 275-287 · Zbl 1081.94541
[8] Jacques Patarin, Cryptoanalysis of the matsumoto and imai public key scheme of eurocrypt ʼ88, in: CRYPTO, 1995, pp. 248-261.; Jacques Patarin, Cryptoanalysis of the matsumoto and imai public key scheme of eurocrypt ʼ88, in: CRYPTO, 1995, pp. 248-261. · Zbl 0868.94025
[9] Faugère, Jean-Charles; Joux, Antoine, Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases, (Boneh, Dan, Advances in Cryptology - CRYPTO 2003. Advances in Cryptology - CRYPTO 2003, Lecture Notes in Comput. Sci., vol. 2729 (2003), Springer), 44-60 · Zbl 1122.94371
[10] Vivien Dubois, Pierre-Alain Fouque, Jacques Stern, Cryptanalysis of sflash with slightly modified parameters, in: EUROCRYPT, 2007, pp. 264-275.; Vivien Dubois, Pierre-Alain Fouque, Jacques Stern, Cryptanalysis of sflash with slightly modified parameters, in: EUROCRYPT, 2007, pp. 264-275. · Zbl 1141.94351
[11] Dubois, Vivien; Fouque, Pierre-Alain; Shamir, Adi; Stern, Jacques, Practical cryptanalysis of sflash, (Menezes, Alfred, CRYPTO. CRYPTO, Lecture Notes in Comput. Sci., vol. 4622 (2007), Springer), 1-12 · Zbl 1215.94043
[12] Aviad Kipnis, Jacques Patarin, Louis Goubin, Unbalanced oil and vinegar signature schemes, in: EUROCRYPT, 1999, pp. 206-222.; Aviad Kipnis, Jacques Patarin, Louis Goubin, Unbalanced oil and vinegar signature schemes, in: EUROCRYPT, 1999, pp. 206-222. · Zbl 0933.94031
[13] Jacques Patarin, Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms, in: EUROCRYPT, 1996, pp. 33-48.; Jacques Patarin, Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms, in: EUROCRYPT, 1996, pp. 33-48. · Zbl 1301.94125
[14] Jean-Charles Faugère, Ludovic Perret, Polynomial equivalence problems: Algorithmic and theoretical aspects, in: EUROCRYPT, 2006, pp. 30-47.; Jean-Charles Faugère, Ludovic Perret, Polynomial equivalence problems: Algorithmic and theoretical aspects, in: EUROCRYPT, 2006, pp. 30-47. · Zbl 1140.94337
[15] Levy dit Vehel, Françoise; Perret, Ludovic, Polynomial equivalence problems and applications to multivariate cryptosystems, (Johansson, Thomas; Maitra, Subhamoy, INDOCRYPT. INDOCRYPT, Lecture Notes in Comput. Sci., vol. 2904 (2003), Springer), 235-251 · Zbl 1123.94006
[16] Bouillaguet, Charles; Faugère, Jean-Charles; Fouque, Pierre-Alain; Perret, Ludovic, Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem, (Catalano, Dario; Fazio, Nelly; Gennaro, Rosario; Nicolosi, Antonio, Public Key Cryptography. Public Key Cryptography, Lecture Notes in Comput. Sci., vol. 6571 (2011), Springer), 473-493 · Zbl 1291.94062
[17] Fouque, Pierre-Alain; Macario-Rat, Gilles; Stern, Jacques, Key recovery on hidden monomial multivariate schemes, (Smart, Nigel P., EUROCRYPT. EUROCRYPT, Lecture Notes in Comput. Sci., vol. 4965 (2008), Springer), 19-30 · Zbl 1149.94313
[18] Wan, Zhexian, On the symplectic invariants of a subspace of a vector space, Acta Math. Sci., 11, 251-253 (1991) · Zbl 0741.15001
[19] Wan, Zhexian, On the orthogonal invariants of a subspace of a vector space over a finite field of odd characteristic, Linear Algebra Appl., 184, 123-133 (1993) · Zbl 0773.15002
[20] Wan, Zhexian, Anzahl theorems in finite singular symplectic, unitary and orthogonal geometries, Discrete Math., 123, 131-150 (1993) · Zbl 0789.05014
[21] Wan, Zhexian, Further studies of singular symplectic, unitary and orthogonal geometries over finite fields, Southeast Asian Bull. Math., 17, 177-196 (1993) · Zbl 0797.51017
[22] Wan, Zhexian, Geometry of Classical Groups over Finite Fields (1993), Science Press · Zbl 0817.51001
[23] Aviad Kipnis, Adi Shamir, Cryptanalysis of the hfe public key cryptosystem by relinearization, in: CRYPTO, 1999, pp. 19-30.; Aviad Kipnis, Adi Shamir, Cryptanalysis of the hfe public key cryptosystem by relinearization, in: CRYPTO, 1999, pp. 19-30. · Zbl 0940.94012
[24] Ding, Jintai; Gower, Jason E.; Schmidt, Dieter, Multivariate Public Key Cryptosystems (Advances in Information Security) (2006), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 1105.94006
[25] Lidl, Rudolf; Niederreiter, Harald, Finite Fields (1997), Cambridge University Press · Zbl 0866.11069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.