Abstract
We propose a new basic trapdoor \(\mathcal{\ell}\)IC (ℓ-Invertible Cycles) of the mixed field type for \(\mathcal{M}\)ultivariate \(\mathcal{Q}\)uadratic public key cryptosystems. This is the first new basic trapdoor since the invention of Unbalanced Oil and Vinegar in 1997. \(\mathcal{\ell}\)IC can be considered an extended form of the well-known Matsumoto-Imai Scheme A (also MIA or C ∗ ), and share some features of stagewise triangular systems. However \({\mathcal{\ell}}\)IC has very distinctive properties of its own. In practice, \({\mathcal{\ell}}\)IC is much faster than MIA, and can even match the speed of single-field \({\mathcal{MQ}}\) schemes.
Chapter PDF
Similar content being viewed by others
References
Akkar, M.-L., Courtois, N.T., Duteuil, R., Goubin, L.: A fast and secure implementation of SFlash. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 267–278. Springer, Heidelberg (2002)
Ioannidis, J., Keromytis, A.D., Yung, M. (eds.): ACNS 2005. LNCS, vol. 3531. Springer, Heidelberg (2005)
Bardet, M., Faugère, J.-C., Salvy, B.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: Proceedings of the International Conference on Polynomial System Solving, pp. 71–74 (2004) (Previously appeared as INRIA report RR-5049)
Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic expansion of the degree of regularity for semi-regular systems of equations. In: Gianni, P. (ed.) MEGA 2005, Sardinia, Italy (2005)
Courtois, N., Goubin, L., Meier, W., Tacier, J.-D.: Solving underdefined systems of multivariate quadratic equations. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 211–227. Springer, Heidelberg (2002)
Courtois, N., Goubin, L., Patarin, J.: Quartz: Primitive specification (second revised version). Submissions, Quartz (October 2001), https://www.cosic.esat.kuleuven.be/nessie
Courtois, N., Goubin, L., Patarin, J.: Sflash: Primitive specification (second revised version). Submissions, Sflash (2002), https://www.cosic.esat.kuleuven.be/nessie
Courtois, N.T., 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), http://www.minrank.org/xlfull.pdf
Stinson, D.R. (ed.): CRYPTO 1993. LNCS, vol. 773. Springer, Heidelberg (1994)
Coppersmith, D., Stern, J., Vaudenay, S.: Attacks on the birational permutation signature schemes. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 435–443. Springer, Heidelberg (1994)
Ding, J., Gower, J.E.: Inoculating multivariate schemes against differential attacks. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 290–301. Springer, Heidelberg (2006), http://eprint.iacr.org/2005/255
Ding, J., Gower, J.E., Schmidt, D., Wolf, C., Yin, Z.: Complexity Estimates for the F 4 Attack on the Perturbed Matsumoto-Imai Cryptosystem. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 262–277. Springer, Heidelberg (2005)
Ding, J.: A new variant of the Matsumoto-Imai cryptosystem through perturbation. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 305–318. Springer, Heidelberg (2004)
Ding, J., Schmidt, D.: Cryptanalysis of HFEv and internal perturbation of HFE. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 288–301. Springer, Heidelberg (2005)
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). Journal of Pure and Applied Algebra 139, 61–88 (1999)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). In: International Symposium on Symbolic and Algebraic Computation — ISSAC 2002, July 2002, pp. 75–83. ACM Press, New York (2002)
Fell, H., Diffie, W.: Analysis of a public key approach based on polynomial substitution. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 340–349. Springer, Heidelberg (1986)
Felke, P.: On the affine transformations of HFE-cryptosystems and systems with branches. Cryptology ePrint Archive, Report 2004/367 (2004), http://eprint.iacr.org/2004/367 , version from 2004-12-17
Fouque, P.-A., Granboulan, L., Stern, J.: Differential cryptanalysis for multivariate schemes. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 341–353. Springer, Heidelberg (2005)
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)
Fulton, W.: Algebraic curves. An introduction to algebraic geometry (a Reprint of 1969 original in Advanced Book Classics). Addison-Wesley Publishing, Redwood City (1989)
Fitzpatrick, P., Wolf, C.: Direct division in factor rings. Electronic Letters 38(21), 1253–1254 (2002), Extended version: http://eprint.iacr.org/2004/353
Goubin, L., Courtois, N.T.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000)
Imai, H., Matsumoto, T.: Algebraic methods for constructing asymmetric cryptosystems. In: Calmet, J. (ed.) Algebraic Algorithms and Error-Correcting Codes. LNCS, vol. 229, pp. 108–119. Springer, Heidelberg (1986)
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999)
Lopéz, J., Dahab, R.: An overview of elliptic curve cryptography. Technical report, Institute of Computing, State University of Campinas, Brazil, 22nd of May 2000. http://citeseer.nj.nec.com/333066.html or http://www.dcc.unicamp.br/ic-tr-ftp/2000/00-14.ps.gz
Computational Algebra Group, University of Sydney. The MAGMA Computational Algebra System for Algebra, Number Theory and Geometry. http://magma.maths.usyd.edu.au/magma/
NESSIE: New European Schemes for Signatures, Integrity, and Encryption. Information Society Technologies programme of the European commission (IST-1999-12324). http://www.cryptonessie.org/ .
Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt ’88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995)
Patarin, J.: Hidden Fields 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), http://www.minrank.org/hfe.pdf
Patarin, J.: The oil and vinegar signature scheme. Presented at the Dagstuhl Workshop on Cryptography, September 1997. transparencies (1997)
Vaudenay, S. (ed.): PKC 2005. LNCS, vol. 3386. Springer, Heidelberg (2005)
Pointcheval, D. (ed.): CT-RSA 2006. LNCS, vol. 3860. Springer, Heidelberg (2006)
Shamir, A.: Efficient signature schemes based on birational permutations. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 1–12. Springer, Heidelberg (1994)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509 (1997)
Tsujii, S., Kurosawa, K., Itoh, T., Fujioka, A., Matsumoto, T.: A public key cryptosystem based on the difficulty of solving a system of nonlinear equations. ICICE Transactions (D) J69-D 12, 1963–1970 (1986)
Wolf, C., Braeken, A., Preneel, B.: Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 294–309. Springer, Heidelberg (2005), http://eprint.iacr.org/2004/237
Wang, L.-C., Hu, Y.-H., Lai, F., Chou, C.y., Yang, B.-Y.: Tractable rational map signature. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 244–257. Springer, Heidelberg (2005)
Wolf, C., Preneel, B.: Asymmetric cryptography: Hidden Field Equations. In: Neittaanmäki, P., Rossi, T., Korotov, S., Oñate, E., Périaux, J., Knörzer, D. (eds.) European Congress on Computational Methods in Applied Sciences and Engineering 2004, Jyväskylä University (2004), Extended version: http://eprint.iacr.org/2004/072/
Wolf, C., Preneel, B.: Equivalent keys in HFE, C*, and variations. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 33–49. Springer, Heidelberg (2005), http://eprint.iacr.org/2004/360/
Wolf, C., Preneel, B.: Taxonomy of public key schemes based on the problem of multivariate quadratic equations. Cryptology ePrint Archive, Report 2005/077, 12th of May 2005. http://eprint.iacr.org/2005/077/
Wang, L.-C., Yang, B.-Y., Hu, Y.-H., Lai, F.: A “medium-field” multivariate public-key encryption scheme. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 132–149. Springer, Heidelberg (2006)
Yang, B.-Y., Chen, J.-M.: All in the XL family: Theory and practice. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 67–86. Springer, Heidelberg (2005)
Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 277–288. Springer, Heidelberg (2004)
Yang, B.-Y., Chen, J.-M.: Building secure tame-like multivariate public-key cryptosystems: The new TTS. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 518–531. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Ding, J., Wolf, C., Yang, BY. (2007). ℓ-Invertible Cycles for \(\mathcal{M}\)ultivariate \(\mathcal{Q}\)uadratic (\({\mathcal{MQ}}\)) Public Key Cryptography. In: Okamoto, T., Wang, X. (eds) Public Key Cryptography – PKC 2007. PKC 2007. Lecture Notes in Computer Science, vol 4450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71677-8_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-71677-8_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71676-1
Online ISBN: 978-3-540-71677-8
eBook Packages: Computer ScienceComputer Science (R0)