The conventional digital signature schemes widely used today may have their security threatened with the possibility of the rising of a large quantum computer. Moreover, such schemes are not entirely suitable for utilization on very constrained-resource platforms. Therefore, there is a need to look at alternatives that present reasonable security in the medium and long term, in addition to attaining acceptable performance when few resources are available. This work provides more efficient multivariate and hash-based post-quantum digital signatures and targets the deployment in scenarios like Internet of Things and Wireless Sensor Networks where the typical devices are very resource-constrained. In the context of multivariable quadratic digital signatures we describe a new technique that attempts to minimize the main drawbacks of these schemes, the large key sizes. The new technique explores certain structures compact matrix rings. Some of the analyzed matrix rings are not secure (one of the attacks runs in polynomial time). Other less compact matrix rings are investigated and they apparently do not suffer a polynomial time attack, but unfortunately are still far from deployment on very constrained platforms. On the other hand, this work describes a method for hash-based signatures providing a 2/3 reduction of the signature sizes in the Merkle-Winternitz multi-time signature scheme. In fact, the signature sizes constitute the main bottleneck of these schemes. The improvement also leads to a 2/3 reduction in the run times (key generation, signing and verifying) and in energy consumption for all these operations on an AVR ATmega128L microcontroller, typically found in Wireless Sensor Networks. This result is much more promising for the deployment in an IoT scenario. / Os esquemas convencionais de assinatura digital mais usados na atualidade têm sua segurança ameaçada com a possibilidade da construção de um computador quântico de grande porte. Ademias, tais esquemas não têm se mostrado completamente adequados para uso em plataformas com recursos computacionais extremamente escassos. Surge então a necessidade da busca por alternativas que satisfaçam as condições de segurança a médio e longo prazo, além de apresentarem desempenho razoável quando poucos recursos computacionais estão disponíveis. Este trabalho obtém assinaturas digitais pós-quânticas multivariadas quadráticas e baseadas em hash mais eficientes e tem o intuito de torna-las práticas em cenários como Internet das Coisas e Redes de Sensores Sem Fio (RSSF), caracterizados por apresentarem dispositivos com recursos computacionais limitados. No contexto de assinaturas multivariadas quadráticas, descreve-se uma nova técnica que tenta minimizar o principal gargalo desses esquemas, o grande tamanho de chaves. A nova técnica explora certos anéis matriciais com estrutura compacta. Mostra-se que alguns dos anéis analisados não são seguros (um dos ataques apresenta tempo polinomial), enquanto outros anéis menos compactos aparentam não sofrer ataque polinomial, mas infelizmente ainda não são adequados para uso em dispositivos muito restritos. Por outro lado, descreve-se um método para obter assinaturas digitais baseadas em hash que fornece redução das assinaturas para 2/3 do tamanho original do esquema multi-time Merkle-Winternitz. De fato, o tamanho das assinaturas constitui o principal gargalo desses esquemas, A melhoria também acarreta uma redução em 2/3 nos tempos de execução (geração de chave, geração de assinaturas e verificação de assinatura) e no consumo de energia para essas operações quando executadas em um microcontrolador AVR tipicamente usado em Redes de Sensores Sem Fio, o AT-mega 128L. Este resultado torna-se promissor para implantação de assinaturas baseadas em hash no cenário de Internet das Coisas.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-08072016-145451 |
| Date | 11 August 2015 |
| Creators | Pereira, Geovandro Carlos Crepaldi Firmino |
| Contributors | Barreto, Paulo Sergio Licciardi Messeder |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | English |
| Detected Language | Portuguese |
| Type | Tese de Doutorado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0024 seconds