In Post-Quantum Cryptography, we are interested in schemes based on problems which are believed to be hard even for quantum computers. 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 2^48 operations, and about 7.2% of the keys using 2^62 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.

Em criptografia pós-quântica, estamos interessados em esquemas criptográficos baseados em problemas cuja solução, acredita-se, não pode ser encontrada eficientemente nem com o uso de computadores quânticos. Esta dissertação, escrita no formato de coletânea de artigos, apresenta contribuições originais sobre a segurança e implementação de três candidatos a esquemas pós-quânticos: HQC, PKP e BIKE. Ambos HQC e BIKE são esquemas de encapsulamento de chaves (KEM) baseados em códigos corretores de erros que foram selecionados pelo NIST como candidatos alternativos em seu processo de padronização de esquemas pós-quânticos. O problema do núcleo permutado (PKP) é um problema NP-difícil que pode ser usado para instanciar esquemas pós-quânticos de assinaturas digitais. A primeira contribuição é um ataque ao HQC usando informações sobre o tempo de execução do algoritmo de encriptação. Este ataque permite a um atacante recuperar a chave privada de uma vítima após medir o tempo de execução de 400 milhões de operações de decriptação, considerando parâmetros para 128 bits de segurança. A segunda contribuição consiste no primeiro ataque a uma generalização do PKP para corpos pequenos. Para parâmetros que prometem 80 bits de segurança, o ataque recupera uma fração de 2^-40 das chaves com apenas 2^48 operações, e aproximadamente 7,2% das chaves com 2^62 operações. A terceira e última contribuição consiste num novo algoritmo de decriptação para o BIKE. O algoritmo foi implementado em tempo constante e observou-se speedups de 1,18, 1,29 e 1,47 em relação ao estado da arte, considerando os níveis de segurança 128, 192, e 256, respectivamente.