Cryptography Reference
In-Depth Information
P
F
q
F
n
+
q
S
T
F
F
n
+
q
F
n
+
q
ϕ
ϕ
−
1
F
F
q
n
+
F
q
n
+
Fig. 1.
The Square Scheme
In the sequel, we will make heavy use of the matrix representation of
M
ulti-
variate
Q
uadratic polynomials. As described above, we assume all polynomi-
als
p
(
k
)
and
f
(
k
)
≤
k
≤
n
+
to be homogenized. As explained, we
can do so as the linear and constant parts of the
p
(
k
)
and
f
(
k
)
do not carry
any cryptographically relevant information. Let
x
=(
x
1
,...,x
n
)
for 1
respectively
n
×
n
x
=(
x
1
,...,x
n
+
)
(
k
)
(
k
)
be a column vector and
P
∈
F
respectively
F
∈
n
+
×
n
+
the matrix describing the quadratic form of
p
(
k
)
=
x
P
(
k
)
x
respec-
F
tively
f
(
k
)
(
k
)
x
. We restrict to symmetric matrices (see figure 2). Using
a minor twist, we can also represent univariate polynomials over the extension
field
=
x
F
F
q
n
this way. By a slight abuse of notation, we obtain the same figure 2
for the univariate polynomial
P
(
k
)
(
X
)=
γ
(
k
)
i,j
X
q
i
+
q
j
over the extension
0
≤
i
≤
j<n
for
x
=(
X, X
q
,...,X
n
−
1
)
.
field
F
q
n
⎛
⎞
γ
(
k
)
1
,
1
γ
(
k
)
γ
(
k
)
1
,
2
/
2
···
···
1
,n
/
2
⎝
⎠
γ
(
k
)
γ
(
k
)
2
,
2
γ
(
k
)
1
,
2
/
2
2
,n
/
2
.
.
.
.
.
.
P
(
k
)
=
γ
(
k
)
1
,n
−
1
/
2
γ
(
k
)
γ
(
k
)
n
−
1
,n
−
1
γ
(
k
)
2
,n
−
1
/
2
n
−
1
,n
/
2
γ
(
k
)
γ
(
k
)
···
γ
(
k
)
γ
(
k
)
n,n
1
,n
/
2
2
,n
/
2
n
−
1
,n
/
2
Fig. 2.
Matrix representation
P
(
k
)
of the public key polynomial
p
(
k
)
3 Double-Layer Square
Double-Layer Square as proposed in [9] uses the idea of Rainbow [11] to split
the central map into two layers and thus destroy the differential properties in
the public map that where used to break Square. The first layer is just the same
mapping
2
n
+
q
n
q
F
as for Square. The second layer is defined by
G
:
F
→
F
with
n
q
=
ϕ
−
1
(
id
×
ϕ
)and
ϕ
:
G
◦
G
◦
F
→
F
q
n
the standard isomorphism. It is
explicitly given by
