Efficient QC-MDPC Cryptosystems with Bounded Decoding Failure Rate

Niederreiter-style post quantum cryptosystems based on QC MDPC codes, such as BIKE, have shown promising efficiency figures and enjoy a straightforward reduction to conjectured-hard problems in coding theory. The longstanding issue in their design is having a closed form Decoding Failure Rate (DFR) analysis of the iterative decoder employed by their decryption primitive, as decoding failures leak information on the private key. State of the art models either provide loose bounds, or do not consider the decoding algorithm employed in practice, using the behavior of a simpler one as a proxy. In this work, we provide a closed form estimate of the DFR for the practically employed three-iterations parallel decoder, applied to QC-MDPC codes. This result constitutes the first closed form DFR model targeting both the same code family and the same decoder employed in the cryptosystem. Leveraging our estimation technique, we design the parameters for a QC-MDPC based Niederreiter encryption scheme, obtaining a 2× improvement in public key and ciphertext size w.r.t. the previous best cryptosystem design with DFR closed-form bounds, LEDAcrypt-KEM. Furthermore, we show that our new parameters yield up to 30% smaller public key size and 2.2× to 4.4× smaller ciphertexts w.r.t. HQC, the code based key encapsulation method selected by the US NIST for standardization, and achieve up to 3× speedup with respect to BIKE in ephemeral and long-term key usage.