Abstract
Square is a multivariate quadratic encryption scheme proposed in 2009. It is a specialization of Hidden Field Equations by using only odd characteristic fields and also X 2 as its central map. In addition, it uses embedding to reduce the number of variables in the public key. However, the system was broken at Asiacrypt 2009 using a differential attack. At PQCrypto 2010 Clough and Ding proposed two new variants named Double-Layer Square and Square+. We show how to break Double-Layer Square using a refined MinRank attack in 245 field operations. A similar fate awaits Square+ as it will be broken in 232 field operations using a mixed MinRank attack over both the extension and the ground field. Both attacks recover the private key, given access to the public key. We also outline how possible variants such as Square– or multi-Square can be attacked.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview 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)
Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 441–458. Springer, Heidelberg (2011)
Billet, O., Gilbert, H.: Cryptanalysis of Rainbow. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 336–347. Springer, Heidelberg (2006)
Billet, O., Macario-Rat, G.: Cryptanalysis of the Square Cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 451–468. Springer, Heidelberg (2009)
Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. Research Series RS-96-33, BRICS, Department of Computer Science, University of Aarhus, pages 39 (September 1996), http://www.brics.dk/RS/96/33/
Chen, C.-H.O., Chen, M.-S., Ding, J., Werner, F., Yang, B.-Y.: Odd-char multivariate hidden field equations. Cryptology ePrint Archive, Report 2008/543 (2008), http://eprint.iacr.org/
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)
Clough, C.L.: Square: A New Family of Multivariate Encryption Schemes. PhD thesis, University of Cincinnati (2009)
Clough, C.L., Ding, J.: Secure Variants of the Square Encryption Scheme. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 153–164. Springer, Heidelberg (2010)
Courtois, N., Goubin, L., Patarin, J.: Sflash: Primitive specification (second revised version) Submissions, Sflash, 11 pages (2002), https://www.cosic.esat.kuleuven.be/nessie
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., dit Vehel, F.L., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008)
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.) AAECC 1985. LNCS, vol. 229, pp. 108–119. Springer, Heidelberg (1986)
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), http://www.minrank.org/hfesubreg.ps , http://citeseer.nj.nec.com/kipnis99cryptanalysis.html
Matsumoto, T., Imai, H., Harashima, H., Miyakawa, H.: A cryptographically useful theorem on the connection between uni and multivariate polynomials. Transactions of the IECE of Japan 68(3), 139–146 (1985)
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
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
Wolf, C., Braeken, A., Preneel, B.: On the security of stepwise triangular systems. Designes, Codes and Cryptography 40(3), 285–302 (2006)
Wolf, C., Preneel, B.: Equivalent keys in multivariate quadratic public key systems. Journal of Mathematical Cryptology 4(4), 375–415 (2011)
Yang, B.-Y., Chen, J.-M.: Rank attacks and defence in Tame-like multivariate PKC’s. Cryptology ePrint Archive, Report 2004/061, September 29, pages 21 (2004), http://eprint.iacr.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Thomae, E., Wolf, C. (2011). Roots of Square: Cryptanalysis of Double-Layer Square and Square+. In: Yang, BY. (eds) Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science, vol 7071. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25405-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-25405-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25404-8
Online ISBN: 978-3-642-25405-5
eBook Packages: Computer ScienceComputer Science (R0)