Cryptography Reference
In-Depth Information
N
k
^
H =
H
F
N−K
Fig. 3.
Parity-check matrix
H
of the code
C
pub
)
de
=
N
+
k
2
x
be in
x
with
σ
in
2
and
2
.Then
Fact 1 .
Let
F
and set
(
σ
||
x
F
x
in
F
σ
is a signature of
x
if and only if:
1.
ˆ
Hx
T
=0
2.
t
1
|
σ
|
t
2
.
The code
C
pub
is of dimension
k
+
K
, and of particular interest is the linear
space
C
sec
⊂ C
pub
that consists in words that satisfy both conditions of Fact 1
and that are obtained by all pairs (
σ,
) of valid message-signature pairs which
are obtained by the secret signature algorithm, that is to say:
C
sec
de
=
(
σ
x
,σ
[1
···N
]
\J
=0
.
N
+
k
2
2
,σ
2
,σ
J
||
x
)
∈
F
:
x
∈
F
∈
F
=
xG
(1)
Clearly, the dimension of
C
sec
is
k
. Additionally, we expect that the weight of
σ
is of order
n/
2 for any (
σ,
x
)in
C
sec
, which is much smaller than the total length
N
. This strongly suggests to use well-known algorithms for finding low weight
codewords to reveal codewords in
C
sec
and therefore message-signature pairs.
The algorithm we used for that purpose is specified in the following subsection.
4.2 Finding Low-Weight Codewords
We propose to use the following variation on Stern's algorithm due to [Dum91]
(See also [FS09]). The description of the algorithm is given in Algorithm 1. It
consists in searching for low-weight codewords among the candidates that are of
very low-weight 2
p
(where
p
is typically in the range 1
4) when restricted
to a set
I
of size slightly larger than the dimension
k
+
K
of the code
p
C
pub
,say
|
=
k
+
K
+
l
for some small integer
l
. The key point in this approach is to
choose
I
among a set
S
of test positions. The set
S
will be appropriately chosen
according to the considered context. If no signature pair is known, then a good
choice for
S
is to take:
I
|
S
=[1
···
N
]
.
(2)
This means that we always choose the test positions among the
N
first positions
of the code
C
pub
and never among the
k
last positions. The reason for this choice
will be explained in the following subsection.
