Exportar registro bibliográfico

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
  • 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
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      PAIVA, Thales Areco Bandiera; TERADA, Routo. Melhorando o ataque de reação contra o QC-MDPC McEliece. 2017.Universidade de São Paulo, São Paulo, 2017. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ >.
    • APA

      Paiva, T. A. B., & Terada, R. (2017). Melhorando o ataque de reação contra o QC-MDPC McEliece. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/
    • NLM

      Paiva TAB, Terada R. Melhorando o ataque de reação contra o QC-MDPC McEliece [Internet]. 2017 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/
    • Vancouver

      Paiva TAB, Terada R. Melhorando o ataque de reação contra o QC-MDPC McEliece [Internet]. 2017 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021