Cryptography Reference
In-Depth Information
1. a full rank binary matrix
H
of size (
N
−
K
)
×
N
with entries in a finite field
F
q
.
2. a subset
J
of
{
1
,...,N
}
of cardinality
n
,
3. a linear code
C
hidden
over
F
q
of length
n
N
and dimension
k
defined by a
generator matrix
n
.Let
t
1
and
t
2
be two integers such that with
very high probability, we have that
t
1
|
u
|
G
of size
k
×
t
2
for any non-zero codeword
u
∈ C
hidden
.
H
The matrix
is chosen such that the best decoding algorithms cannot solve
the following search problem.
N−K
q
Problem 1.
Given the knowledge of
s
∈
F
which is the syndrome by
H
of
q
some
e
∈
F
whose weight lies in [
t
1
···
t
2
], find explicitly
e
, or eventually
x
in
q
F
different from
e
sharing the same properties as
e
.
de
=
T
. The Kabatianskii-
Krouk-Smeets (KKS) signature scheme is then described in Figure 1.
Finally let
F
be the (
N
−
K
)
×
k
matrix defined by
F
H
J
G
-
Setup.
1. The signer
S
chooses
N
,
Kn
,
k
,
t
1
and
t
2
according to the required security
level.
2.
S
draws a random (
N − K
)
× N
matrix
H
.
3.
S
randomly picks a subset
J
of
{
1
,...,N}
of cardinality
n
.
4.
S
randomly picks a random
k × n
generator matrix
G
that defines a code
C
hidden
such that with high probability
t
1
|
u
|
t
2
for any non-zero codeword
u
∈ C
hidden
.
5.
F
de
=
H
J
G
T
where
H
J
is the restriction of
H
to the columns in
J
.
-
Keys.
•
Private key.
J
and
G
•
Public key.
F
and
H
-
Signature.
The signature
σ
of a message
x
∈
F
q
is defined as the unique vector
σ
of
F
q
such that
σ
i
=0forany
i ∈ J
and
σ
J
=
xG
.
Given (
x
,σ
)
∈
F
q
×
F
q
, the verifier checks that
-
Verification.
t
1
|σ|
t
2
and
H
σ
T
=
Fx
T
.
Fig. 1.
Description of the KKS scheme given in [KKS97]
The scheme was modified in [BMJ11] to propose a one-time signature scheme
by introducing two new ingredients, namely a hash function
f
and adding an
error vector
to the signature. It was proved that such a scheme is EUF-1CMA
secure in the random oracle model. The description is given in Figure 2.
e
4
Description of the Attack
The purpose of this section is to explain the idea underlying our attack which
aims at recovering the private key. The attack is divided in two main steps.
