Cryptography Reference
In-Depth Information
reveals a part of the secret transformation
T
. The crucial point is to calculate
the probability over all
ω
that there exist values
λ
1
,...,λ
n
+
∈
F
q
such that
ker
n
+
λ
i
S
F
(
i
)
S
ω
∈
.
(4)
i
=1
2
n
+
q
For
S
being an (2
n
+
)
×
(2
n
+
) matrix of full rank and
ω
∈
R
F
this
probability equals the likelihood of
n
+
(
i
)
Sω
∈
ker
λ
i
F
.
(5)
i
=1
While the general idea is the same for Double-Layer Square, we need to be careful
as
S
is a (2
n
+
)
2
n
matrix of rank 2
n
. We will tackle this problem after having
calculated the probability that there exists
λ
i
∈
F
q
fulfilling (5).
It is well known that the probability of a random (
m
×
n
)matrixover
×
F
q
being regular is given by
1
<
1
m
−
1
q
i
q
n
1
q
n
−
m
+1
.
−
−
(6)
i
=0
This implies that the probability of a random (
m
×
n
)matrixover
F
q
to be
singular is bounded below by 1
/
(
q
n
−
m
+1
). In Fig. 4 we illustrate the coecient
matrix of the linear system
n
+
(
i
)
2
n
+
(
i
)
+
λ
i
F
λ
i
G
Sω
=0
(7)
i
=1
i
=
n
+
+1
2
n
+
and for
g
(
i
)
=
x
G
(
i
)
x
the associated matrix
for a random but fixed
ω
∈
F
for a given secret polynomial
g
(
i
)
.
n
n
+
F
(1)
Sω
.
F
(
n
+
)
Sω
G
(
n
+
+1)
Sω
.
0
A
B
G
(2
n
+
)
Sω
Fig. 4.
Coecient matrix of linear system (7)
The probability that there exist
λ
1
,...,λ
n
+
∈
F
q
such that (5) holds is the
probability of matrix
A
in figure 4 to be singular,
i.e.
1
/q
. Note that it is not
