Cryptography Reference
In-Depth Information
(K+k+l)/2
(K+k+l)/2
N−K−l
HH
0
l
1
2
1
1
0
H
...
N−K−l
3
0
1
Fig. 4.
A parity-check matrix for
C
pub
in quasi-systematic form
ˆ
C
pub
contains
C
sec
as a subcode and its codewords represent valid message-signature pairs. This
subcode has actually a very specific structure that helps greatly the attacker:
H
Indeed, the parity-check matrix
displays peculiar properties:
1. There are many codewords in
C
sec
,namely2
k
.
2. The support of these codewords is included in a fixed (and rather small) set
of size
k
+
n
.
3.
k
positions of this set are known to the attacker.
4. These codewords form a linear code (of dimension
k
).
Because of all these properties, the aforementioned attack will work much better
than should be expected from a random code. More precisely, let us bring in:
I
de
=
I
∩
J.
Notice that the expectation
E
{|I
|}
of the cardinality of the set
I
is equal to:
n
N
(
k
+
K
+
l
)=(
R
+
αρ
+
λ
)
n
I
|}
E
{|
=
(3)
whereweintroducedthefollowingnotation:
K
N
,
k
n
,
n
N
l
N
.
R
de
=
ρ
de
=
α
de
=
λ
de
=
and
The point is that whenever there is a codeword
c
in
C
sec
which is such that
|
c
I
|
=2
p
we have a non-negligible chance to find it with Algorithm 1. This does
not hold with certainty because the algorithm does not examine all codewords
x
such that
=2
p
, but rather it consists in splitting
I
in
I
1
and
I
2
of the same
size and looking for codewords
|
x
I
|
x
such that
|
x
I
1
|
=
|
x
I
2
|
=
p
. In other words, we
consider only a fraction
δ
of such codewords where:
δ
=
(
K
+
k
+
l
)
/
2
(
K
+
k
+
l
)
/
2
p
(
K
+
k
+
l
)
πp
(
K
+
k
+
l
p
K
+
k
+
l
2
p
≈
2
p
)
.
−
