Roots of Square: Cryptanalysis of Double-Layer Square and Square - Post-Quantum Cryptography - page 83

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

Enrico Thomae and Christopher Wolf

Horst Görtz Institute for IT-security
Faculty of Mathematics
Ruhr-University of Bochum, 44780 Bochum, Germany
http://www.cits.rub.de/
{enrico.thomae,christopher.wolf}@rub.de, [e-mail]

Abstract. Square is a multivariate quadratic encryption scheme pro-
posed 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 vari-
ants named Double-Layer Square and Square+ . We show how to break
Double-Layer Square using a refined MinRank attack in 2 45 field oper-
ations. 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.

Keywords: Multivariate Cryptography, Algebraic Cryptanalysis, Square,
Double-Layer Square, Square+, MinRank, Key Recovery.

1 Introduction

In the world of Post-Quantum cryptography, uadratic public key

schemes have an important place. They were investigated as early as 1985 [14, 16]
and have branched out into several systems.
In this article, we deal with the so-called Square system, which works both
over a ground field

M ultivariate Q

F q with q elements, as over an extension field F q n + .Itsmain

feature is the operation X 2 over

F q n + . Obviously, this is very simple to compute
and invert—in particular when compared to the similar system Hidden Field
Equations [17]. Inversion of X 2 utilizes the equation X =

q n + +1
4

± Y . Hence, we

need q n + ≡ 3 (mod 4) and inverting Y ∈ F q requires only one exponentiation

in F q n + . Depending on the choice of q, n , the inversion is as ecient as for

Sflash [1, 10].
Square itself was proposed 2009 in [7]. It was broken in the same year [4] using
a differential attack. At PQCrypto 2010 Clough and Ding [9] proposed two new
variants of Square, called Double-Layer Square and Square+ which are claimed