Melhorando o ataque de reação contra o QC-MDPC McEliece (2017)
- Authors:
- Autor USP: PAIVA, THALES ARECO BANDIERA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2018.tde-07012018-212020
- Subjects: COMPUTABILIDADE E COMPLEXIDADE; CRIPTOLOGIA
- Keywords: Ataque de reação; Criptografia pós-quântica; Post-quantum cryptography; QC-MDPC; QC-MDPC; Reaction attack
- Agências de fomento:
- Language: Português
- Abstract: O QC-MDPC McEliece foi considerado um dos mais promissores esquemas criptográficos de chave pública que oferecem segurança contra ataques por computadores quânticos. O tamanho das chaves públicas do QC-MDPC McEliece é competitivo com o das chaves do RSA, e o esquema tem uma redução de segurança aparentemente forte. Por três anos, o esquema não sofreu ataques críticos, até que na Asiacrypt de 2016 Guo, Johansson, e Stankovski mostraram um ataque de reação contra o QC-MDPC McEliece que explora um aspecto não considerado em sua redução de segurança: a probabilidade de o algoritmo de decriptação falhar é menor quando a chave secreta e o vetor usado para encriptar a mensagem compartilham certas propriedades, chamadas de espectros. Dessa forma, um atacante pode, ao detectar falhas de decriptação, obter informação sobre o espectro, que será usada para reconstruir a chave secreta. Guo et al. apresentaram um algoritmo para a reconstrução da chave a partir do espectro recuperado, para o qual é possível apontar três problemas. O primeiro é que seu algoritmo não é eficiente quando o espectro da chave não foi recuperado quase completamente, o que resulta em o atacante ter que enviar um grande número de testes de decriptação à portadora da chave secreta. O segundo problema é que o desempenho de seu algoritmo não escala bem para níveis de segurança mais altos. O terceiro e último problema é que, por ser baseado numa busca em profundidade, seu algoritmo não pode ser paralelizadotrivialmente. Para aumentar a eficiência do ataque, dois novos algoritmos de reconstrução são propostos neste trabalho. Estes algoritmos são mais eficientes, usam menos informação sobre a chave secreta, e podem ser paralelizados trivialmente. O primeiro algoritmo é probabilístico e tem complexidade assintótica ligeiramente melhor do que a do original. Entretanto, o desempenho do algoritmo probabilístico piora rapidamente, embora mais lentamente do que o algoritmo de Guo et al., conforme a quantidade de informação sobre o espectro diminui. O segundo algoritmo explora uma relação linear entre os blocos da chave secreta. Este é mais eficiente, tanto assintoticamente quanto na prática, que os dois outros algoritmos, e é eficiente mesmo com 50% menos informação sobre o espectro do que o necessário para o algoritmo original. Isso permite que o atacante encontre a chave secreta fazendo apenas em torno de 20% do número de testes necessários pelo algoritmo de Guo\'s et al., considerando-se o nível de segurança de 80 bits. O desempenho de ambos os algoritmos são analisados e comparados com o do algoritmo original, e as análises são feitas tanto para a complexidade teórica quanto para o desempenho na prática, considerando a implementação dos algoritmos em linguagem C
- Imprenta:
- Data da defesa: 11.12.2017
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
PAIVA, Thales Areco Bandiera. Melhorando o ataque de reação contra o QC-MDPC McEliece. 2017. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2017. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/. Acesso em: 11 abr. 2026. -
APA
Paiva, T. A. B. (2017). Melhorando o ataque de reação contra o QC-MDPC McEliece (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ -
NLM
Paiva TAB. Melhorando o ataque de reação contra o QC-MDPC McEliece [Internet]. 2017 ;[citado 2026 abr. 11 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ -
Vancouver
Paiva TAB. Melhorando o ataque de reação contra o QC-MDPC McEliece [Internet]. 2017 ;[citado 2026 abr. 11 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ - Attacking and defending post-quantum cryptography candidates
- Cryptanalysis of the binary permuted kernel problem
- Two algorithms to improve the reaction attack on the QC-MDPC McEliece
- A timing attack on the HQC encryption scheme
- Robust covert channels based on DRAM power consumption
- Faster constant-time decoder for MDPC codes and applications to BIKE KEM
- BGP anomalies classification using features based on AS relationship graphs
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
