Cryptography Reference
In-Depth Information
(
k
)
Replacing
P
on the left hand side with the public key matrices
P
for 1
≤
k
≤
(
n
+
+
p
), plugging in the definitions of
C
,
A
, and bringing the matrix
T
to the
left we obtain
(1)
M
n
+
S
,...,SM
n
+
F
(
n
+
)
M
n
+
S
)
M
−
1
(1)
,...,
P
(
n
+
+
p
)
)
T
−
1
=[(
SM
n
+
F
(
P
n
+
(
SA
(1)
S
,...,SA
(
p
)
S
)]
||
Again, “||” denotes the concatenation of vectors. Note that the
overall
equa-
tion is over the ground field
(
i
)
F
q
, while the matrices
F
are over the extension
n
+
field
q
. There are two important remarks to be made: First, the matrices
A
(
i
)
are with overwhelming probability of high rank, both over the ground field
and the extension field
F
(1)
M
n
+
S
has
F
q
n
+
. In contrast, each column
SM
n
+
F
at most rank 1 over the extension field
F
q
n
+
. Note that the embedding modifier
does
not
change the latter rank property as the rank will only decrease, not
increase by the embedding modifier, cf. [2, Sect. 5] for a more detailed expla-
nation of this fact. Second, we are only interested in separating out the first
(
n
+
) columns of the right hand side from the last
p
ones. So we do not look
for the full matrix
T
−
1
, but only its first (
n
+
) columns. We denote them by
T
(
n
+
+
p
)
×
(
n
+
)
q
and have rank
n
+
. Combining these two observations, our
equation simplifies to
∈
F
(
n
+
)
M
n
+
S
)
Note that the
whole
equation is now over the extension field while the coecients
of the matrices
(
n
+
+
p
)
)
TM
n
+
=(
SM
n
+
F
(1)
M
n
+
S
,...,SM
n
+
F
(1)
,...,
P
(
P
(
i
)
come from the ground field. For simplicity, write
U
:=
TM
n
+
.Byconstructionof
M
n
+
P
=
u
i,j
−
1
and
u
i,
1
=
u
i,n
+
we have
u
i,j
for
1
≤
i
≤
n
+
,
1
<j
≤
n
+
, so the knowledge of
one
column of
U
is enough to
determine the whole matrix. Hence we only concentrate on the first column of
U
and obtain
n
+
+
p
i
=1
P
M
n
+
S
=:
H
with
H
(
i
)
(1)
n
×
n
q
n
+
u
i,
1
=
SM
n
+
F
∈
F
n
+
q
for unknown
S
. As our final equation is over
1
and can thus use a similar technique as in section 3 to determine values
λ
i
∈
F
q
n
+
such that
F
we clearly have rank(
H
)
≤
n
+
+
p
(
i
)
)
rank(
λ
i
P
≤
1
i
=1
by solving the corresponding MinRank(
q, n
+
+
p,
1) problem,
i.e.
for rank
r
=1.
4.2 Solving MinRank for Square+
All in all, there are two methods available. The first is credited to Schnorr and
works on determinants for (
r
+1)
(
r
+ 1) submatrices while the other was
developed by Levy-dit-Vehel
et al.
[12] and uses Gröbner bases.
×
