Cryptography Reference
In-Depth Information
-
Setup.
1. The signer
S
chooses
N
,
Kn
,
k
,
t
1
and
t
2
according to the required security
level.
2.
S
chooses a hash function
f
:
{
0
,
1
}
∗
×
F
N−K
2
−→
F
2
.
3.
S
draws a random binary (
N − K
)
× N
matrix
H
.
4.
S
randomly picks a subset
J
of
{
1
,...,N}
of cardinality
n
.
5.
S
randomly picks a
k×n
generator matrix
G
that defines a binary code
C
hidden
such that with high probability
t
1
|
u
|
t
2
for any non-zero codeword
u
∈ C
hidden
.
6.
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
∈{
0
,
1
}
∗
is (
h, σ
) defined as follows:
• S
picks a random
e
∈
F
2
such that
|
e
|
=
n
.
•
Let
h
de
=
f
(
x
,
He
T
)and
y
be the unique vector of
F
2
such that (i)
supp
(
y
)
⊂
J
, (ii)
y
J
=
hG
. The second part of the signature
σ
is then given by
σ
de
=
y
+
e
.
-
Verification.
Given a signature (
∈
F
2
×
F
2
}
∗
, the verifier checks
h
,σ
)
for
x
∈{
0
,
1
x
,
H
σ
T
+
Fh
T
).
that
|σ|
2
n
and
h
=
f
(
Fig. 2.
Description of the scheme of [BMJ11]
First, we produce a valid signature for some message using only the public key.
To do so, we define a certain code from matrices
. It turns out that low
weight codewords of this code give valid message-signature pairs. Then we just
apply Dumer's algorithm [Dum91] in order to find these low weight codewords.
Thisattackcanevenberefinedinthefollowing way. Whenever we are able to
produce one valid message-signature pair, and since each signature reveals partial
information about the private key (especially about
J
as explained further in
this section), we can use it to get another valid message-signature pair revealing
more information about
J
. We repeat this process a few times until we totally
recover the whole private key. More details will be given in the following sections.
In what follows, we make the assumption that all the codes are binary because
all the concrete proposals are of this kind. The non-binary case will be discussed
in the conclusion.
H
and
F
4.1 An Auxiliary Code
We give here the first ingredient we use to forge a valid message/signature pair
for the KKS scheme just from the knowledge of the public pair
. This attack
can also be used for the second scheme given by Figure 2. In the last case, it
is not a valid message/signature pair anymore but an auxiliary quantity which
helps in revealing
J
. This ingredient consists in a linear code
H
,
F
C
pub
of length
N
+
k
defined as the kernel of
ˆ
H
which is obtained by the juxtaposition of
the two public matrices
as given in Figure 3. The reason behind this
definition lies in the following Fact 1.
H
and
F
