Cryptography Reference
In-Depth Information
the extension field
F
q
n
+
. This way we can apply the homomorphism
F
q
n
+
→
:
x
→
x
q
k
for
k
=0
,...,
(
n
+
−
F
q
n
+
1) within the extension field. Finally, this
is used to construct a matrix
M
n
+
.
⎛
⎞
... θ
q
n
+
−
1
1
θ
1
θ
1
⎝
⎠
θ
2
... θ
q
n
+
−
1
θ
2
2
.
.
.
.
.
θ
n
+
θ
n
+
... θ
q
n
+
−
1
M
n
+
:=
n
+
n
+
q
More precisely, for a vector
v
:= (
v
1
,...,v
n
+
l
)
∈
F
we have the mapping
φ
:
n
+
q
F
→
F
q
n
+
with
φ
(
v
)
→
V
1
:(
v
1
,...,v
n
+
)
M
n
+
=: (
V
1
,...,V
n
+
)
.
Note that this mapping only uses the first component of the vector (
V
1
,...,V
n
+
).
Moreover, the first column of
M
n
+
consists only of base elements of
n
+
q
F
. Hence,
V
1
∈
F
q
n
n
q
are the same. The inverse mapping needs to make use of the special struc-
ture of the matrix
M
n
+
to map elements back into the ground field. We have
φ
−
1
:
two values
V
1
,
will only be equal if the corresponding vectors
v, v
∈
F
n
+
q
F
q
n
+
→
F
for
(
v
1
,...,v
n
+
):(
V, V
q
,...,V
q
n
+
−
1
)
M
−
1
φ
−
1
(
V
)
→
n
+
=: (
v
1
,...,v
n
+
)
.
Using the matrix
M
n
+
, we can now go back and forth between the two vec-
tor spaces
n
+
q
n
+
(extension field). The latter is a very
redundant version of the former as we could use any component of the vector
V
=(
V, V
q
,...,V
q
n
+
−
1
) to reconstruct all other (
n
+
−
n
+
q
F
(ground field) and
F
1) elements. However,
we will see below how it will help us to express the rank condition on
F
using
only publicly available information.
There are two minor ingredients missing before we can formulate the full
attack. The first is the quadratic form of the plus polynomials
a
1
,...,a
p
.Asfor
Double-Layer Square, we write them as symmetric matrices
A
(
i
)
(
n
+
)
×
(
n
+
)
∈
F
q
with
x
=(
x
1
,...,x
n
+
)and
a
i
=
xA
(
i
)
x
for 1
≤
i
≤
p
. Hence, we work over
(
n
+
)
×
(
n
+
)
q
n
+
(
i
)
the ground field here. Second, we define matrices
F
∈
F
similar
(
i
)
k,k
(
i
)
a,b
to
F
from above as
F
:= 1 but
F
=0for
k
:= (1
−
i
)(mod
n
+
)+1,
1
≤
a, b
≤
k
. Or to rephrase this, we have the all-zero matrix with the a single
1, the matrix
(1)
,andthe1is
traveling backwards on the main diagonal for each consecutive matrix
F
coincides with the originally defined matrix
F
(
i
)
.Note
F
(
k
)
M
n
+
that evaluating
M
n
+
F
yields exactly
X
2
for each matrix
F
(
k
)
.
We now express the private key in terms of
S, T, A,
F
and study their corre-
sponding ranks
P
=
T
◦
F
◦
S
=(
C◦
S,
A◦
S
)
T
