Cryptography Reference
In-Depth Information
that the latter problem can be solved in the range of parameters used in the
CFS signature algorithm. This does not prove that their proposal is insecure.
However, it invalidates the hypotheses of their security proof. The main diculty
in suggesting a CFS type scheme is to come up with a family of very high rate
codes with an ecient decoding algorithm and whose structure can be hidden
in the same way as in the McEliece scheme. This narrows down quite a bit the
families of codes which can be used in this setting and up to now only Goppa
codes are known to meet this goal. It should be emphasized that it is precisely
their rich algebraic structure which makes it possible to distinguish them from
random codes.
On the other hand, the KKS proposal does not rely on Goppa codes and
can be instantiated with random codes. Moreover, unlike in the CFS signature
scheme, it does not compute a signature by using a decoding algorithm for the
code and thus completely avoids the necessity of having to use restricted families
of codes with a “hidden” trapdoor. Moreover, a variation of it has been proposed
in [BMJ11] and has been proved to be EUF-1CMA secure in the random oracle
model. The security of the KKS scheme has been investigated in [COV07]. It
was shown that a passive attacker who may intercept just a few signatures can
recover the private key. All the schemes proposed in [KKS97] can be broken
in this way with the help of at most 20 signatures. Basically it uses the fact
that a valid message-signature pair reveals on average half of the secret support
J
(see Section 3 where this set is defined precisely). Therefore with
O
(log
)
message-signature pairs it is expected to recover the whole set
J
. The security
of the scheme is not compromised by this attack however if only one signature
is computed, and this especially in the variant proposed in [BMJ11] where some
random noise is added on top of the signature.
The purpose of this article is to present a completely new security analysis of
the KKS scheme and its variant proposed in [BMJ11]. Our approach for breaking
the scheme is to define a certain error correcting code from the couple of public
matrices used in the scheme and to notice that certain rather low weight code-
words give actually valid signatures. It is therefore natural to use standard algo-
rithms for finding low-weight codewords in this setting, such as Stern's algorithm
[Ste88] or its Dumer variant [Dum96, FS09] (see also [BLP11]). It turns out that
such algorithms are unusually successful in this setting due to the conjunction of
three factors: (i) there are many low-weight codewords, (ii) they are localized on
a rather small support, (iii) some part of this support is known to the attacker.
It appears that all parameters suggested in [KKS97, KKS05, BMJ11] are easily
broken by this approach and this without even knowing a single signature pair.
Moreover, this approach can exploit the knowledge of a message-signature pair
which speeds up the attack.
We provide an analysis of this attack which explains what makes it feasible for
the parameters proposed in [KKS97, KKS05, BMJ11]. The KKS scheme relies
on a couple of matrices which can be viewed as parity-check matrices of two
linear codes. We show that when the first code has a rate which is smaller than
the rate of the second one (or has approximately the same rate), then our attack
is quite successful. This was exactly the case for all the parameters suggested
|
J
|
