Attacking and defending post-quantum cryptography candidates

• Ano de defesa: 2022
• Autor(a) principal: Paiva, Thales Areco Bandiera
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Ataque por tempo de execução; BIKE; Constant-time implementation; Criptanálise; Criptografia pós-quântica; Cryptanalysis; HQC; Implementação em tempo constante; PKP; Post-quantum cryptography; Timing attack
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-30012023-200916/

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.