An Efficient Attack on All Concrete KKS Proposals
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 proven to be EUF-1CMA secure in the random oracle model. In this paper, the authors investigate the security of these schemes and suggest a simple attack based on (essentially) Stern's algorithm for finding low weight codewords. It efficiently recovers the private key of all schemes of this type existing in the literature. This is basically due to the fact that they 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.