Attacking and defending post-quantum cryptography candidates

This dissertation, which is written as a collection of papers, presents original contributions to the security and implementation of three post-quantum cryptography candidates: HQC, PKP and BIKE. Both HQC and BIKE are code-based key encapsulation mechanisms that were selected as alternate candidates in NIST’s post-quantum standardization process. The Permuted Kernel Problem (PKP) is an NP-hard combinatorial problem that can be used to instantiate post-quantum digital signature schemes. The first contribution is a timing attack against HQC that allows an attacker to recover the secret key after recording the decryption time of around 400 million ciphertexts, for 128 bits of security. The second contribution consists of the first attack targeting a generalization of PKP for small fields. For 80-bit security parameters, the attack is able to recover a fraction 2−40 of the keys using only 248 operations, and about 7.2% of the keys using 262 operations. The third and last contribution consists of a new decryption algorithm for BIKE. Our constant-time implementation of this algorithm achieves speedups of 1.18, 1.29 and 1.47, with respect to state-of-the-art decryption algorithms, for security levels 128, 192 and 256, respectively.