Cryptography Reference
In-Depth Information
2No on
In this section we shortly recap the Square encryption scheme [7]. We start by
giving some general outline on
M
ultivariate
Q
uadratic public key systems and
some notation.
Each
n
q
m
q
MQ
-scheme uses a public
M
ultivariate
Q
uadratic map
P
:
F
→
F
with
⎛
⎝
⎞
⎠
p
(1)
(
x
1
,...,x
n
)
.
p
(
m
)
(
x
1
,...,x
n
)
P
:=
for 1
≤
k
≤
m
and
γ
(
k
)
p
(
k
)
(
x
1
,...,x
n
):=
ij
x
i
x
j
1
≤
i
≤
j
≤
n
n
q
m
q
as public key. The trapdoor is given by a structured central map
F
:
F
→
F
with
⎛
⎞
f
(1)
(
x
1
,...,x
n
)
.
f
(
m
)
(
x
1
,...,x
n
)
⎝
⎠
F
:=
for 1
≤
k
≤
m
and
≤
i
≤
j
≤
n
γ
(
k
)
f
(
k
)
(
x
1
,...,x
n
):=
ij
x
i
x
j
.
1
In order to hide this trapdoor we choose two secret linear transformations
S
∈
n
×
n
q
m
×
m
q
F
:=
T
◦F ◦
S
. Note that some proposals also use
a linear and constant part of
p
(
k
)
and
f
(
k
)
. However, as it is well known that
quadratic terms only depend on quadratic terms from the secret map
,T
∈
F
and define
P
and on
linear terms from
S, T
, we can safely ignore the linear and constant parts in our
cryptanalysis to ease explanation [3, 15, 18]. Where necessary, the ane case
can be added easily.
Sometimes, as for Square, the trapdoor does not reveal itself over
F
q
F
but over
n
+
q
→
F
q
n
+
be the standard isomorphism
between the vector space and the extension field and
the extension field
F
q
n
+
.Let
ϕ
:
F
F
=
ϕ
◦F ◦
ϕ
−
1
.As
outlined above, Square is defined for
q
n
+
F
=
X
2
≡
3 (mod 4) and uses
over
F
q
n
+
. This can be easily inverted by the square root formula
±
Y
q
n
+
+1
X
=
.
(1)
4
To make their scheme more resistant, the authors of Square have chosen
S
as
a(
n
+
)
×
n
matrix of rank
n
. This is equivalent to deleting
variables from
the secret map
. See figure 1 for an overall illustration of
Square. The original parameters of the scheme are
n
=34
,q
=31and
=3[7].
F
in the public map
P
