Attacks and vulnerabilities on NewHope KEM and small-Ring-LWE problem (2024)
- Authors:
- Autor USP: VILLENA, REYNALDO CACERES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2024.tde-13122024-193342
- Subjects: CRIPTOLOGIA; ALGORITMOS; SEGURANÇA DE COMPUTADORES; SEGURANÇA DE REDES
- Keywords: Criptografia pós-quântica; NewHope KEM; Post-quantum cryptography; Problema Ring-LWE; Ring-LWE problem
- Agências de fomento:
- Language: Inglês
- Abstract: Existem sistemas criptográficos que são seguros contra ataques de computadores clássicos e quânticos. Um desses sistemas é o NewHope KEM (key encapsulation mechanism) que usa como base o problema Ring-Learninng with errors (Ring-LWE). Esse problema presume-se que seja difícil de resolver, mesmo em um computador quântico. Um esquema KEM permite compartilhar uma chave comum entre duas partes (Alice & Bob). Esta tese apresenta contribuições originais para a segurança e análise de ataques de incompatibilidade de chaves e de vazamento de informações no NewHope KEM, Além disso, são mostradas algumas vulnerabilidades no problema small-Ring-LWE (que é uma variante do problema Ring-LWE). A primeira contribuição contém algumas melhorias nos principais ataques de incompatibilidade de chaves propostos por Bauer et al. e Qin et al. (Bauer et al., 2019; Qin et al., 2019). Esses ataques de incompatibilidade de chave recuperam a chave secreta de Alice. Propomos dois novos métodos chamados métodos Fast Qin e Double Qin. Os métodos Fast Qin e Double Qin requerem cerca de 240k e 34k consultas a um oráculo, respectivamente; em vez de 840k consultas do método de Qin et al. Além disso, adaptamos esses dois novos métodos para recuperar a chave secreta de Alice no NewHope-512 (uma variante do NewHope). A segunda contribuição analisa o vazamento de informações sobre a chave secreta de Bob no NewHope, quando ela é reutilizada. Nosso resultado corrobora que a chave secreta de Bob não deve serreutilizada, pois com duas comunicações com Bob, a chave secreta dele é revelada. No problema Ring-LWE, um polinômio a é selecionado aleatoriamente e um polinômio b é calculado b = a.s + e onde s é o polinômio secreto (selecionado aleatoriamente) e o e é um polinômio de ruído. Nossa terceira contribuição mostra que no small-Ring-LWE, variante do Ring-LWE onde os polinômios s e e são pequenos, existem valores do parâmetro público a que vazam uma grande porcentagem dos coeficientes do segredo s. E, a última contribuição mostra que o segredo s pode ser recuperado com sucesso se pelo menos 50% dos coefficientes aleatórios de s e e são conhecidos
- Imprenta:
- Data da defesa: 18.10.2024
- 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
VILLENA, Reynaldo Cáceres. Attacks and vulnerabilities on NewHope KEM and small-Ring-LWE problem. 2024. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-13122024-193342/. Acesso em: 14 abr. 2026. -
APA
Villena, R. C. (2024). Attacks and vulnerabilities on NewHope KEM and small-Ring-LWE problem (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-13122024-193342/ -
NLM
Villena RC. Attacks and vulnerabilities on NewHope KEM and small-Ring-LWE problem [Internet]. 2024 ;[citado 2026 abr. 14 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-13122024-193342/ -
Vancouver
Villena RC. Attacks and vulnerabilities on NewHope KEM and small-Ring-LWE problem [Internet]. 2024 ;[citado 2026 abr. 14 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-13122024-193342/ - Reconstrução da Chave secreta do RSA multi primo
- Vulnerability: information leakage of reused secret key in NewHope
- The importance of the public global parameter on Ring-LWE problem-based key encapsulation mechanims
- Recovering the secret on binary Ring-LWE problem with random known bits
- Recovery of the secret on Binary Ring-LWE problem using random known bits: extended version
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
