Cryptography Reference
In-Depth Information
We will therefore obtain all codewords
c
in
C
sec
which are such that
|
c
I
1
|
=
C
sec
of
|
c
I
2
|
=
p
. Consider now the restriction
C
sec
to the positions belonging to
I
,thatis:
C
sec
=
(
x
i
)
i∈
[1
···N
+
k
]
∈ C
sec
.
x
i
)
i∈I
:
x
=(
(4)
Thecrucialissueisnowthefollowingquestion:
C
sec
Does there exist in
a codeword of weight
2
p
?
The reason for this is explained by the following proposition.
Proposition 1.
Let
I
s
de
=
I
s
∩
x
in
J
for
s
∈{
1
,
2
}
. If there exists a codeword
C
sec
|
x
I
1
|
|
x
I
2
|
such that
=
=
p
, then it will be the restriction of a codeword
x
in
C
sec
which will belong to the list
L
output by Algorithm 1.
x
in
C
sec
such that
|
x
I
1
|
|
x
I
2
|
Proof.
Consider a codeword
=
=
p
.For
s
∈{
1
,
2
}
,
extend
x
I
s
with zeros on the other positions of
I
s
and let
x
s
be the corresponding
word. Notice that
x
1
and
x
2
will be considered by Algorithm 1 and
x
1
will
1
. By definition of
x
,(
be stored at the address
H
1
x
x
1
||
x
2
) is the restriction
N−K−l
2
of a codeword
x
of
C
sec
to
I
,say
x
=(
x
1
||
x
2
||
y
)with
y
∈
F
.Since
be the matrix obtained from
ˆ
C
sec
⊂ C
pub
we have
ˆ
T
=0.Let
ˆ
put in
quasi-systematic form through a Gaussian elimination as given in Figure 4. We
also have
ˆ
Hx
H
H
T
= 0 and hence:
H
x
1
+
2
=0
H
1
x
H
2
x
(5)
and
x
1
||
x
2
)
T
+
T
H
3
(
y
=0
.
(6)
2
and will be considered
Equation (5) shows that
x
1
is stored at address
H
2
x
at Step 8 of the algorithm. In this case,
x
will be stored in
L
.
C
sec
is still
k
and that this code behaves like
a random code of the same length and dimension. Ignoring the unessential issue
whether or not
x
satisfies
We expect that the dimension of
|
x
I
1
|
|
x
I
2
|
=
=
p
, let us just assume that there exists
x
C
sec
such that
|
x
|
in
=2
p
. There is a non negligible chance that we have
|
x
I
1
|
|
x
I
2
|
=
p
and that this codeword will be found by our algorithm. The
issue is therefore whether or not there is a codeword of weight 2
p
in a random
code of dimension
k
and length
=
I
|
|
. This holds with a good chance (see [BF02]
for instance) as soon as:
I
|
2
p
d
GV
(
|
,k
)
(7)
I
|
where
d
GV
(
|
,k
) denotes the Gilbert-Varshamov distance of a code of length
I
|
|
and dimension
k
. Recall that [MS86]:
I
|
h
−
1
(1
I
|
I
|
d
GV
(
|
,k
)
≈
−
k/
|
)
|
