Este trabalho tem por objetivo estudar reticulados, com foco em aplicacoes a esque- mas de criptografia. A importancia deste estudo vem do fato que varios metodos de criptografia baseada em reticulados sao conjecturados resistentes a ataques em computa- dores quanticos, uma vez que os metodos mais classicos sao comprovadamente suscetiveis. Criptografia baseada em reticulados e uma das atuais sub-areas da chamada criptografia pos-quantica, que, independente do advento dos computadores quanticos, visa tambem uma maior eficiencia e seguranca nos computadores atuais. [...]
Este trabalho tem por objetivo estudar reticulados, com foco em aplicacoes a esque- mas de criptografia. A importancia deste estudo vem do fato que varios metodos de criptografia baseada em reticulados sao conjecturados resistentes a ataques em computa- dores quanticos, uma vez que os metodos mais classicos sao comprovadamente suscetiveis. Criptografia baseada em reticulados e uma das atuais sub-areas da chamada criptografia pos-quantica, que, independente do advento dos computadores quanticos, visa tambem uma maior eficiencia e seguranca nos computadores atuais. [...]
Avanços na construção de computadores quânticos e o fato de vários dos atuais padrões criptográficos serem inseguros na presença de um eventual computador quântico de maior porte levaram o NIST a promover um concurso de padronização de algoritmos pós-quânticos, caracterizados pela segurança em computadores convencionais e quânticos. Neste trabalho são comparados esquemas de assinatura digital baseada em reticulados que participam da segunda fase do concurso, com base nas propriedades, segurança e desempenho dos algoritmos.
Sistemas criptográficos clássicos, como o RSA e o ElGamal, mostraram ser vulneráveis na presença de um computador quântico suficientemente poderoso. Dada esta descoberta, a comunidade científica focou a sua atenção no desenvolvimento e estudo de alternativas imunes a arquiteturas quânticas. Sistemas baseados em treliças são um dos criptossistemas que se provou serem resistentes a ataques por parte de computadores quânticos. Estes criptossistemas baseiam a sua segurança em problemas matemáticos duros, como o Problema do Vetor mais Curto (Shortest Vector Problem, SVP), Problema do Vetor mais Próximo (Closest Vector Problem, CVP), e outros. Assim sendo, o estudo de algoritmos desenhados para resolver estes problemas -- também conhecidos como ataques -- é de extrema importância, com o objetivo de os entender melhor, e por forma a melhor selecionar os parâmetros de construção destes criptossistemas. O foco desta dissertação é um tipo específico de ataque: algoritmos baseados em célula de Voronoi, que são frequentemente mencionados na literatura como sendo impráticos, mas que têm sido alvo de muito pouca pesquisa, especialmente quando comparados com outros tipos. Nesta dissertação, várias otimizações para um algoritmo baseado em célula de Voronoi são propostas, com o objetivo de reduzir tanto o tempo de execução, como os requisitos de memória das implementações. De modo a aproveitar todo o poder computacional disponível nos computadores modernos, versões paralelas em CPU, GPU e heterogénea CPU + GPU são propostas, apresentando ganhos lineares no primeiro caso (e algum benefício com Hyper-Threading), e reportando ganhos de 13.37x e 15.03x, para as versões GPU e heterogénea, respetivamente, quando comparadas com a versão sequencial base em CPU. Adicionalmente, diversas variantes heurísticas com implementações paralelas em CPU são propostas, com o intuito de acelerar a computação da solução do SVP, com a melhor estratégia de "poda" desenvolvida a alcançar ganhos até 256.51x, usando 8 threads (quando comparada com a versão sequencial base em CPU), calculando a solução correta para 99.84% das bases testadas. Finalmente, conduzida no âmbito desta dissertação, a integração de todo o trabalho na biblioteca Lattice Unified Set of Algorithms (LUSA) -- um projeto que ambiciona disponibilizar acesso público a uma coleção de implementações rápidas e fáceis de utilizar, de algoritmos relacionados com treliças. Os resultados obtidos nesta dissertação mostram, ainda que longe das dimensões do estado da arte, que é possível acelerar imensamente um algoritmo baseado em célula de Voronoi, mantendo taxas de sucesso extremamente elevadas.
Em um sistema de criptografia funcional, uma autoridade de posse de uma chave mestra pode gerar uma chave secreta que permite o calculo de uma funcao sobre a mensagem nos dados criptografados. Assim, e possivel calcular tal funcao no texto cifrado usando somente a chave secreta. Exemplos importantes de criptografia funcional sao Criptografia Baseada em Identidades, Criptografia Baseada em Atributos, Criptografia com Produto Escalar, Criptografia Difusa Baseada em Identidades, Criptografia de Vector Oculto, Criptografia Baseada em Certificados, Criptografia com Pesquisa de Palavra-Chave e Criptografia Baseada em Identidades com Curinga. Esquemas de criptografia com predicados sao uma especializacao de esquemas de criptografia funcionais, em que a funcao utilizada nao fornece informacoes sobre a mensagem, mas determina se a decriptacao deve ou nao funcionar corretamente. Criptografia baseada em reticulados e uma importante alternativa para os principais sistemas criptograficos utilizados atualmente, uma vez que elas sao supostamente seguras contra algoritmos quânticos. O Algoritmo de Shor e capaz de resolver o Problema da Fatoracao Inteira e o Problema do Logaritmo Discreto em tempo polinomial em um computador quântico, quebrando os sistemas criptograficos mais usados e importantes atualmente, como o RSA, o Diffie-Hellman e a Criptografia de Curvas Elipticas. Neste trabalho nos concentramos em esquemas de criptografia com predicados baseados em reticulados. Nos estudamos e descrevemos os principais sistemas baseados em reticulados encontrados na literatura, estendendo-os a versoes hierarquicas e mostrando como o uso de um reticulado com estrutura ideal afeta a prova de seguranca. Para cada esquema, uma prova formal de seguranca e detalhada, as analises de complexidade e do tamanho das variaveis sao mostradas e a escolha dos parâmetros garantindo o funcionamento correto da decriptacao e dada.
Abstract
Redes veiculares viabilizam diversas aplicações importantes, como direção autônoma e prevenção de acidentes de tráfego, as quais exigem um alto nível de segurança nas comunicações. No entanto, para se comunicarem de forma protegida, essas redes se apoiam em algoritmos criptográficos vulneráveis a ataques dos futuros computadores quânticos, o que exige a adoção de alternativas mais seguras. Entretanto, os algoritmos de criptografia pós-quântica já padronizados têm se mostrado incompatíveis com as rigorosas exigências de latência impostas por tais redes, dificultando sua adoção. Nesse trabalho, identificamos alguns dos principais desafios em aberto na área, a partir da análise de padrões estabelecidos e trabalhos recentes, e apresentamos oportunidades de pesquisa para a superação dos mesmos.
Nos dias atuais, os sistemas de criptografia e autenticação desempenham um papel fundamental em aplicações que envolvem a manipulação de informações sigilosas, tais como movimentações financeiras, comércio eletrônico, aplicações militares e proteção de arquivos digitais. A popularização do uso dos sistemas de criptografia e autenticação se deve, em grande parte, a descrição de esquema de criptografia por chave pública. A segurança de tais sistemas é baseada na intratabilidade computacional (clássica) de problemas da teoria dos números, como a fatoração em produtos de primos e o problema do logaritmo discreto. A partir da formulação da Mecânica Quântica, foram demonstrados algoritmos que, executados em um computador quântico e consumindo tempo e recursos polinomiais, são capazes de resolver tais problemas. A construção de um computador quântico inviabilizaria, portanto, o uso de sistemas de criptografia e autenticação por chave pública. Nesta dissertação é discutido o problema da autenticação quântica de mensagens clássicas. É proposto um protocolo híbrido que alcança segurança incondicional, mesmo que um criptoanalista disponha de recursos computacionais infinitos, sejam eles clássicos ou quânticos. Através de uma prova matemática formal, é mostrado que o nível de segurança pode ser feito tão alto quanto desejado. Tal segurança é-garantida pelos princípios fundamentais da mecânica quântica.
Com a possível chegada do primeiro computador quântico operacional que poderá quebrar a segurança de algoritmos criptográficos assimétricos tradicionais, as entidades responsáveis por promover a segurança de dados têm se mobilizado a oferecer uma resposta para tal advento. Existem diversas propostas para um novo padrão de criptografia pós-quântica, cada uma baseada em um método matemático diferente. Este trabalho avalia as principais propostas que participam da segunda rodada do Processo de Padronização Criptográfica Pós-Quântica do NIST, apresentando as performances de umas em relação às outras. O objetivo deste artigo é ajudar usuários a fazer uma escolha mais informada.