On the Hardness of Decoding Quasi-Cyclic Codes and the Security of Code-Based Public-Key Cryptosystems

Post-quantum public key encryption (PKE) schemes employing Quasi-Cyclic (QC) sparse parity-check matrix codes are enjoying significant success, thanks to their good performance profile and significant reduction in the keypair size. However, there is no formal proof that the hardness of decoding random QC codes is related to the decoding hardness of random codes, which is known to be NP-hard, nor that changing the (constant in the length) rate of the employed QC codes does not change the nature of the underlying hard problem. In this work, we address and solve these challenges, answering both of them in the affirmative. First, we prove computational equivalences among hard problems from coding theory and the corresponding problems for QC codes. Then, we provide a systematization of hard problems and security assumptions underlying QC-MDPC-based cryptosystems, proving that fixing the rate of the QC codes does not change the hardness of key recovery attacks. These results allow the design of Niederreiter-style QC-MDPC PKEs, with the additional flexibility granted by freely choosing the code rate, leading to code-based public key encryption schemes which are both secure and can be fit in very demanding scenarios, such as embedded systems.