Efficient methods for lattice-based cryptography (2015)
- Authors:
- Autor USP: BARGUIL, JOÃO MARCOS DE MATTOS - EP
- Unidade: EP
- Sigla do Departamento: PCS
- Subjects: CRIPTOLOGIA; RETICULADOS; ALGORITMOS
- Language: Inglês
- Abstract: Reticulados têm sido aplicados de diferentes maneiras em criptografia. Inicialmente utilizados para a destruição de criptossistemas, eles foram posteriormente aplicados na construção de novos esquemas, incluindo criptossistemas assimétricos, esquemas de assinatura cega e os primeiros métodos para encriptação completamente homomórfica. Contudo, seu desempenho ainda é proibitivamente ruim em muitos casos. Neste trabalho, expandimos técnicas originalmente desenvolvidas para encriptação homomórfica, tornando-as mais genéricas e aplicando-as no esquema GGH-YK-M, um esquema de chave pública, e no esquema LMSV, a única construção homomórfica que não sucumbiu a ataques de recuperação de chaves IND-CCA1 até o momento. Em nossos testes, reduzimos o tamanho das chaves do GGH-YK-M em uma ordem de complexidade, especificamente, de O(n2 lg n) para O(n lg n), onde n é um parâmetro público esquema. A nova técnica também atinge processamento mais rápido em todas as operações envolvidas em um criptossistema assimétrico, isto é, geração de chaves, encriptação e decriptação. A melhora mais significativa é na geração de chaves, que se torna mais de 3 ordens de magnitude mais rápida que resultados anteriores, enquanto a encriptação se torna por volta de 2 ordens de magnitude melhor. Para decriptação, nossa implementação é quatro vezes mais rápida que a literatura. Também mostramos que é possível aumentar a segurança do esquema LMSV contra os ataques quânticos de recuperação de chaves recentemente publicados pela agência britânica GCHQ. Isso é feito através da adoção de reticulados não-ciclotômicos baseados em anéis polinomiais irredutíveis quase-circulantes. Em nossa implementação, o desempenho da encriptação é virtualmente idêntico, e a decriptação torna-se ligeiramente inferior, um pequeno preço a se pagar pelo aumento de segurança.A geração de chaves, porém, é muito mais lenta, devido à necessidade de se utilizar um método mais genérico e caro. A existência de métodos dedicados altamente eficientes para a geração de chaves nesta variante mais segura do LMSV permanece como um problema em aberto.
- Imprenta:
- Data da defesa: 14.08.2015
-
ABNT
BARGUIL, João Marcos de Mattos. Efficient methods for lattice-based cryptography. 2015. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2015. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3141/tde-12072016-083255/. Acesso em: 01 out. 2024. -
APA
Barguil, J. M. de M. (2015). Efficient methods for lattice-based cryptography (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3141/tde-12072016-083255/ -
NLM
Barguil JM de M. Efficient methods for lattice-based cryptography [Internet]. 2015 ;[citado 2024 out. 01 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3141/tde-12072016-083255/ -
Vancouver
Barguil JM de M. Efficient methods for lattice-based cryptography [Internet]. 2015 ;[citado 2024 out. 01 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3141/tde-12072016-083255/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas