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
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
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://www.teses.usp.br/teses/disponiveis/45/45134/tde-13122024-193342/. Acesso em: 22 jan. 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://www.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 jan. 22 ] Available from: https://www.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 jan. 22 ] Available from: https://www.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
- Recovery of the secret on Binary Ring-LWE problem using random known bits: extended version
- Recovering the secret on binary Ring-LWE problem with random known bits
Informações sobre o DOI: 10.11606/T.45.2024.tde-13122024-193342 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
