Cryptography Reference
In-Depth Information
To prove this lemma, we will introduce the following notation and lemma. For
x
2
for some arbitrary
s
,
=(
x
i
)
1
i
s
and
y
=(
y
i
)
1
i
s
being two elements of
F
we define
x
·
y
as
=
1
i
s
x
·
y
x
i
y
i
,
the addition being performed over
F
2
.
2
and choose
Lemma 2.
Let
x
and
y
be two different and nonzero elements of
F
2
,then
h
uniformly at random in
F
=0)=
1
2
prob
(
x
·
h
(12)
=0)=
1
4
prob
(
x
·
h
=0
,
y
·
h
(13)
2
:
Proof.
To prove Equation (12) we just notice that the subspace
{
h
∈
F
x
·
h
=
1. There are therefore 2
n−
1
solutions to this equation and
0
}
is of dimension
n
−
=0)=
2
n−
1
2
n
=
1
prob
(
x
·
h
2
.
On the other hand, the hypothesis made on
x
and
y
implies that
x
and
y
2
and that the dual space, that is
generate a subspace of dimension 2 in
F
{
h
∈
2
:
F
x
·
h
=0
,
y
·
h
=0
}
is of dimension
n
−
2. Therefore
=0)=
2
n−
2
2
n
=
1
4
prob
(
x
·
h
=0
,
y
·
h
Proof (of Lemma 1).
Let
h
1
,...,
h
n−k
be the
n
−
k
rows of
H
rand
.Then
T
prob
(
x
∈ C
rand
)=
prob
(
H
rand
x
=0)
=
prob
(
h
1
·
x
=0
,...,
h
n−k
·
x
=0)
=
prob
(
h
1
·
x
=0)
...
prob
(
h
n−k
·
x
= 0)
(14)
=2
k−n
(15)
where Equation (14) follows by the independence of the events and Equation
(15) uses Lemma 2. Equation (11) is obtained in a similar fashion.
2
of size
m
and let
f
be the function
Lemma 3.
Let
X
be some subset of
F
defined by
f
(
x
)
de
=max
x
(1
x
.Wedenoteby
x
the quantity
1
m
2
n
−
k
,
−
x/
2)
,
1
−
then
prob
(
X
∩ C
rand
=
∅
)
≥
f
(
x
)
.
Proof.
For
x
in
X
we define
E
x
as the event “
x
belongs to
C
rand
”andwelet
q
de
=2
k−n
.Wefirstnoticethat
prob
(
X
∩ C
rand
=
∅
)=
prob
E
x
.
x
∈X
