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
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
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.
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.
Os algoritmos criptográficos pós-quânticos têm como premissa de segurança a dificuldade na resolução de problemas matemáticos que se conjecturam difíceis na computação quântica. O interesse em implantar esses algoritmos tem vindo a crescer por forma a que a informação esteja protegida contra ataques quânticos no futuro. O National Institute of Standards and Technology (NIST) tem, atualmente, aberto um concurso para a seleção de algoritmos criptográficos pós-quânticos [1]. Nesta dissertação estuda-se dois desses algoritmos, mais precisamente, os esquemas de assinatura digital qTESLA e Crystals-Dilithium, tendo como ferramenta principal, no que concerne à implementação não otimizada dos mesmos, o software SageMath. Embora o concurso da NIST seja um passo importante, é relevante que exista uma transição dos protocolos atuais para um novo modelo, integrando soluções híbridas. Nesse sentido, e tendo em vista uma melhor transição dos algoritmos clássicos, analisa-se a adaptação dos certificados à criptografia pós-quântica e faz-se a experimentação de certificados híbridos com os esquemas de assinatura já mencionados. Este trabalho foi desenvolvido em parceria com a Universidade do Minho e a Multicert.
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. [...]
A seguranca de dados e fundamental para a execucao de diversas tarefas do cotidiano, seja acessar contas bancarias ate o funcionamento de carros autonomos. Algoritmos de criptografia, existente desde o inicio dos tempos em diferentes formas, foram criados para garantir a integridade destes dados. Um dos algoritmos de seguranca mais utilizados, o Rivest-Shamir-Adleman (RSA) tornou importante a fatoracao, para saber qual o estado da arte da criptografia e saber quanto tempo levara para fatorar numeros muito grandes, que e o que torna o RSA seguro atualmente. Ha diversas implementacoes de algoritmos de fatoracao, porem, nenhum apresenta uma eficiencia adequada para quebrar a criptografia RSA. No entanto, com o avanco da computacao quântica, como uma necessidade fisica resultante do encolhimento dos chips de processamento dos computadores, a seguranca da informacao e colocada em cheque com o Algoritmo de Shor, desenvolvido por Peter Shor na decada de 1990, que e mais eficiente que os algoritmos classicos de fatoracao, e pode ser capaz de quebrar a criptografia RSA em tempo habil no futuro. O objetivo do presente artigo e apresentar uma analise de diferentes algoritmos de fatoracao classicos e compara-los com o Algoritmo de Shor para mostrar as falhas de seguranca que existirao na era da computacao quântica.
A ascensão da computação quântica representa uma ameaça existencial para a criptografia de chave pública contemporânea, cujos pilares, como RSA e a criptografia de curvas elípticas (ECC), são vulneráveis ao Algoritmo de Shor. Este artigo explora a transição da geometria elíptica clássica para uma nova classe de primitivas criptográficas resistentes a ataques quânticos, com foco na criptografia baseada em isogenias de curvas elípticas supersingulares. Analisamos como as propriedades geométricas das curvas elípticas, que foram a base para a segurança pré-quântica, são reimaginadas no contexto pós-quântico. O problema do logaritmo discreto em curvas elípticas (ECDLP), a base da ECC, é substituído pelo problema computacionalmente mais robusto de encontrar uma isogenia entre duas curvas supersingulares. Investigamos a arquitetura de protocolos como o Supersingular Isogeny Diffie-Hellman (SIDH) e seu derivado, Supersingular Isogeny Key Encapsulation (SIKE), destacando suas vantagens, como o tamanho reduzido das chaves em comparação com outras propostas pós-quânticas. No entanto, também abordamos a recente quebra criptoanalítica do SIKE, que, embora devastadora, revelou novas direções de pesquisa e a importância de uma análise de segurança contínua. Concluímos que, apesar dos reveses, a geometria de curvas elípticas e as isogenias continuam a ser uma área promissora e fundamental na busca por uma infraestrutura criptográfica segura na era quântica, motivando o desenvolvimento de esquemas mais robustos e a exploração de problemas matemáticos relacionados.