Cryptography Reference
In-Depth Information
An Ecient Attack
on All Concrete KKS Proposals
Ayoub Otmani
1
,
2
and Jean-Pierre Tillich
1
1
SECRET Project - INRIA Rocquencourt
Domaine de Voluceau, B.P. 105 78153 Le Chesnay Cedex - France
{
ayoub.otmani,jean-pierre.tillich
}
@inria.fr
2
GREYC - Universit´edeCaen-Ensicaen
Boulevard Marechal Juin, 14050 Caen Cedex, France
Abstract.
Kabastianskii, Krouk and Smeets proposed in 1997 a digital
signature scheme based on a couple of random error-correcting codes.
A variation of this scheme was proposed recently and was proved to
be EUF-1CMA secure in the random oracle model. In this paper we
investigate the security of these schemes and suggest a simple attack
based on (essentially) Stern's algorithm for finding low weight codewords.
It eciently recovers the private key of all schemes of this type existing
in the literature. This is basically due to the fact that we can define
a code from the available public data with unusual properties: it has
many codewords whose support is concentrated in a rather small subset.
In such a case, Stern's algorithm performs much better and we provide
a theoretical analysis substantiating this claim. Our analysis actually
shows that the insecurity of the proposed parameters is related to the
fact that the rates of the couple of random codes used in the scheme
were chosen to be too close. This does not compromise the security of the
whole KKS scheme. It just points out that the region of weak parameters
is really much larger than previously thought.
Keywords:
Code-based cryptography, digital signature, random error-
correcting codes, cryptanalysis.
1
Introduction
Digital signature schemes are probably among the most useful cryptographic
algorithms. If quantum computers were to become reality, it would be useful
to devise such schemes which would resist to it. A possible approach to meet
this goal could be to build such schemes whose security relies on the diculty
of decoding linear codes. Two code based schemes of this kind have been pro-
posed, namely the Courtois-Finiasz-Sendrier signature scheme [CFS01] and the
Kabatianskii, Krouk and Smeets (KKS) scheme [KKS97, KKS05].
The Courtois-Finiasz-Sendrier (CFS) scheme presents the advantage of hav-
ing an extremely short signature and its security has been proven to rely on
the well-known syndrome decoding problem and the distinguishability of binary
Goppa codes from a random code. However, it has been proved in [FGO
+
10]
