Paper 2011/431

Roots of Square: Cryptanalysis of Double-Layer Square and Square+

Enrico Thomae and Christopher Wolf

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 2^45 field operations. A similar fate awaits Square+ as it will be broken in 2^32 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. PQCrypto 2011
Keywords
Multivariate CryptographyAlgebraic CryptanalysisSquareDouble-Layer SquareSquare+MinRankKey Recovery
Contact author(s)
enrico thomae @ rub de
christopher wolf @ rub de
History
2011-10-04: revised
2011-08-12: received
See all versions
Short URL
https://ia.cr/2011/431
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/431,
      author = {Enrico Thomae and Christopher Wolf},
      title = {Roots of Square: Cryptanalysis of Double-Layer Square and Square+},
      howpublished = {Cryptology ePrint Archive, Paper 2011/431},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/431}},
      url = {https://eprint.iacr.org/2011/431}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.