Cryptography Reference
In-Depth Information
P
F
q
F
n
+
+
p
q
S
T
CA
F
n
+
q
F
n
+
+
p
q
Fig. 5.
The Double-Layer Square Scheme
C◦
S,
A◦
S
). See
figure 5 for a graphical representation. Note that all intermediate operations are
quadratic over
Now we can write the public key
P
of Square+ as
P
:=
T
◦
(
. If we leave out the embedding modifier for a moment
(transformation
S
), there are two parts of Square+, namely the invertible, but
“soft” part
X
2
, represented by transformation
F
q
,asis
P
C
, and the not-invertible “hard”
part
a
1
,...,a
p
, represented by transformation
. If we manage to separate them,
we are done as there is an ecient attack against Square [2].
A
4.1 Odd-Characteristic HFE Attack against Square+
To this aim, we have a closer look at “odd Characteristic HFE” (or odd-HFE)
and its cryptanalysis [2, 6]. In particular we notice that the central map of odd-
HFE is
γ
i,j
X
q
i
+
q
j
(
i,j
)
∈
Δ
(
D
)
2
:
i
≤
j, q
i
+
q
j
for a set of admissible degrees
Δ
(
D
):=
(
i, j
)
∈
N
≤
D
}
N
the
set of non-negative integers and
γ
i,j
∈
F
q
n
the coecients of the corresponding
private key. Setting
D
=2and
γ
(0
,
0)
=1,weobtain
Δ
(2) = (0
,
0) and the central
map of odd-HFE coincides with the one of Square+. As a result, we can apply
the cryptanalysis of Bettale
et al.
[2] against odd-HFE also against Square+.
Alas, this cryptanalysis does not include the case odd-HFE+, so we need to
investigate this question closely to determine if we can break Square+ within
this framework. As we will see below, it works but there are subtle changes to
be made.
As for the original attack against odd-HFE, the key point is the observation
that we can write
X
2
as a matrix of small rank over the
extension
field. More
to the point, we have
X
2
=
x
F
x
over
{
,
for
x
=(
X, X
q
,X
q
2
,...,X
q
n
−
1
)
F
q
n
+
with
F
1
,
1
= 1 but
F
i,j
= 0 otherwise. As only
F
1
,
1
is non-zero, we obviously
have rank(
) = 1. A similar observation for a MinRank attack against HFE was
already used by Kipnis-Shamir [15]. Note that expressing
X
2
F
over the ground
field yields a much higher rank, in practice close to (
n
+
).
To ease notation and to mount the attack, we follow the approach of [2] and
start with the vector (
θ
1
,...,θ
n
+
)
n
+
q
n
+
. Note that this vector has a double
function: First, it fixes a basis of the vector space
∈
F
n
+
q
,
i.e.
over the ground
field, and second, the elements
θ
1
,...,θ
n
+
are simultaneously interpreted over
F
