Security and complexity of the McEliece cryptosystem based on quasi‐cyclic low‐density parity‐check codes

摘要

In the context of public key cryptography, the McEliece cryptosystemrepresents a very smart solution based on the hardness of the decoding problem,which is believed to be able to resist the advent of quantum computers. Despitethis, the original McEliece cryptosystem, based on Goppa codes, has encounteredlimited interest in practical applications, partly because of some constraintsimposed by this very special class of codes. We have recently introduced avariant of the McEliece cryptosystem including low-density parity-check codes,that are state-of-the-art codes, now used in many telecommunication standardsand applications. In this paper, we discuss the possible use of a bit-flippingdecoder in this context, which gives a significant advantage in terms ofcomplexity. We also provide theoretical arguments and practical tools forestimating the trade-off between security and complexity, in such a way to givea simple procedure for the system design.