On Decoding Schemes for the MDPC-McEliece Cryptosystem
This work addresses security and efficiency issues in post-quantum cryptography for cryptographers and system designers, but it is incremental as it builds on existing MDPC-McEliece frameworks.
The paper tackles the problem of improving decoding schemes for the MDPC-McEliece cryptosystem by analyzing classical iterative decoders and proposing new message-passing algorithms, resulting in improved error-correction performance and resilience against a specific key-recovery attack.
Recently, it has been shown how McEliece public-key cryptosystems based on moderate-density parity-check (MDPC) codes allow for very compact keys compared to variants based on other code families. In this paper, classical (iterative) decoding schemes for MPDC codes are considered. The algorithms are analyzed with respect to their error-correction capability as well as their resilience against a recently proposed reaction-based key-recovery attack on a variant of the MDPC-McEliece cryptosystem by Guo, Johansson and Stankovski (GJS). New message-passing decoding algorithms are presented and analyzed. Two proposed decoding algorithms have an improved error-correction performance compared to existing hard-decision decoding schemes and are resilient against the GJS reaction-based attack for an appropriate choice of the algorithm's parameters. Finally, a modified belief propagation decoding algorithm that is resilient against the GJS reaction-based attack is presented.