• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
10.11606/D.3.2016.tde-12072016-083255
Document
Auteur
Nom complet
João Marcos de Mattos Barguil
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2015
Directeur
Jury
Barreto, Paulo Sergio Licciardi Messeder (Président)
Aranha, Diego de Freitas
Misoczki, Rafael
Titre en portugais
Métodos eficientes para criptografia baseada em reticulados.
Mots-clés en portugais
Algoritmos
Criptografia
Criptografia pós-quântica
Encriptação homomórfica
Reticulados
Resumé en portugais
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 lenta 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 encriptação 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 do 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 mais rápida. Para decriptação, nossa implementação é dez 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.
Titre en anglais
Efficient methods for lattice-based cryptography.
Mots-clés en anglais
Cryptography
Homomorphic encryption
Lattices
Post-quantum cryptography
Resumé en anglais
Lattices have been applied in many different ways in cryptography. Firstly used for the destruction of cryptosystems, they were later applied in the construction of new schemes, including asymmetric cryptosystems, blind signature schemes and the first methods for fully homomorphic encryption. Nonetheless, performance is still prohibitively slow in many cases. In this work, we expand techniques originally devised for homomorphic encryption, making them more general and applying them to the GGH-YK-M cryptosystem, a lattice-based public-key cryptosystem, and to the LMSV scheme, the only known homomorphic scheme that has not succumbed to INDCCA1 key recovery attacks to this date. In our tests, we reduce public key bandwidth occupation of GGH-YK-M by an order of complexity, specifically, from O(n2 lg n) down to O(n lg n) bits, where n is a public parameter of the scheme. The new technique also attains faster processing in all operations involved in an asymmetric cryptosystem, that is, key generation, encryption, and decryption. The most significant improvement in performance is in key generation, which becomes more than 3 orders of magnitude faster than previous results, while encryption becomes about 2 orders of magnitude faster. For decryption, our implementation is ten times faster than the literature. We also show that it is possible to improve security of LMSV against the quantum key recovery attacks recently published by British GCHQ.We do so by adopting non-cyclotomic lattices based on nearly-circulant irreducible polynomial rings. In our implementation, performance of encryption remains virtually the same, and decryption becomes slightly worse, a small price to pay for the improved security. Key generation, however, is much slower, due to the fact that it is necessary to use a more generic and expensive method. The existence of highly effcient dedicated methods for key generation of this secure variant of LMSV remains as an open problem.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2016-07-13
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.