The tightness of security reductions in code-based cryptography
Nicolas Sendrier · 2011
Code-based cryptography allows the construction of primitives with various functionalities. Those designs are in general secure and possess no undesirable features that cannot be corrected by a proper choice of parameters and a careful implementation (i.e. semantically secure conversion). Their security reduction is, for the systems who do not require a trapdoor decoder, as good as possible as we have an exact reduction to the syndrome decoding problem, the hardness of which conveys an extreme confidence. For public-key systems (encryption, signature) there exists no really threatening (non exponential) attacks but the security reduction involves other problems (indistinguishability of families of codes) which offer some confidence but which also need to be considered with more hindsight, in particular for variants with reduced key size (typically using quasi-cyclic or quasi-dyadic codes). The security reductions of code-based cryptosystems rely on well identified problems and in that sense are well founded. We hope that the problems we expose here will attract some attention and eventually help to produce even better reductions.