Criptografia baseada em isogenias supersingulares constitui uma das famílias mais recentes dentre as propostas resistentes a ataques com computadores quânticos. Destaca-se sua baixa ocupação de banda em comparação a outros protocolos de acordo de chave, potencializada pela possibilidade de compressão de chaves ao custo de uma sobrecarga significativa no tempo de processamento. Neste trabalho, sugerem-se técnicas eficientes para minimizar os principais gargalos de processamento envolvidos na compressão e descompressão de chaves. Em conjunto, essas técnicas produzem ganhos observados de até três vezes em relação aos melhores resultados de técnicas anteriormente propostas.
Criptografia baseada em isogenias supersingulares constitui uma das famílias mais recentes dentre as propostas resistentes a ataques com computadores quânticos. Destaca-se sua baixa ocupação de banda em comparação a outros protocolos de acordo de chave, potencializada pela possibilidade de compressão de chaves ao custo de uma sobrecarga significativa no tempo de processamento. Neste trabalho, sugerem-se técnicas eficientes para minimizar os principais gargalos de processamento envolvidos na compressão e descompressão de chaves. Em conjunto, essas técnicas produzem ganhos observados de até três vezes em relação aos melhores resultados de técnicas anteriormente propostas.
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.
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.
Resumo A criptografia clássica utiliza suposições de dificuldade computacional, como a fatoração de grandes números, para garantir segurança na comunicação. Tal uso pode ser comprometido por avanços de hardware ou software, como a implementação do algoritmo de Shor pela computação quântica. O trabalho em tela explora a segurança da criptografia quântica atrelada inteiramente às leis da mecânica quântica, em um contexto no qual busca-se gerar, de forma segura, chaves clássicas por meios quânticos com a Distribuição Quântica de Chaves para posterior uso em algoritmos como o one-time-pad. A pesquisa teve foco na QKD dependente de equipamentos, mais especificamente dentro da categoria de preparação e medição, contemplando implementações práticas do protocolo de seis estados feitas no IBM Quantum Experience platform. Explora-se cenários ideais, ruidosos, com e sem adversários, analisando os resultados através do QBER. O trabalho abrange ainda conceitos sobre os procedimentos de pós-processamento de reconciliação da informação e amplificação privada, mencionando eventuais ataques quânticos e suas contramedidas, citando a distribuição quântica de chaves independente de dispositivos como uma das possíveis abordagens de solução.
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
AGRADECIMENTOSAgradeço inicialmente à minha orientadora, Prof. a Cíntia Margi, por ter acreditado em meu potencial e ter aceito me orientar em um trabalho tão fora da sua área de atuação.Seus conselhos e ensinamentos foram, sem dúvida, essenciais para a realização deste trabalho.Seu empenho em buscar referências, se manter por dentro do trabalho e dar críticas a este foram fundamentais para a melhoria do trabalho.Sou especialmente grato pela abertura sempre existente para discutir qualquer assunto, desde pesquisa e ensino até àqueles não relacionados ao mestrado.Também não poderia deixar de citar toda a ajuda durante o processo seletivo para o doutorado, ou talvez devesse dizer, os processos seletivos, além é claro de todas as indicações e referências após minha aceitação.Espero ter correspondido a altura e ter preenchido as expectativas, no sentido intelectual e na dedicação.Também agradeço ao Prof. Paulo Barreto, que desempenhou extra-oficialmente um papel de coorientação em meu trabalho.Agradeço inicialmente por ter indicado o tema e o problema a serem abordados.As discussões em diversos momentos ajudaram a sanar dúvidas e mostrar o caminho a ser seguido na execução deste trabalho.Agradeço ao Laboratório de Arquitetura e Redes de Computadores, todos seus membros, e em especial ao Prof. Wilson Ruggiero, por ter me acolhido durante a realização do mestrado.Não apenas pelo apoio material recebido, mas especialmente pelo ótimo ambiente aqui encontrado.Hoje posso dizer que me sinto parte dessa grande família.Gostaria de agradecer aos membros da banca Prof. José Roberto Piqueira e Dr. José Eduardo Moreira, que aceitaram participar de minha avaliação, agradeço por seus comentários que ajudaram a enriquecer este trabalho e diminuir suas falhas.Também, agradeço ao Prof. Carlos Molina Mendes pela revisão e pelos comentários que foram de grande utilidade para a melhora deste manuscrito.Adicionalmente, gostaria de agradecer ao membros do SEMBEI, grupo de pesquisa do qual tenho a honra de fazer parte.Cada um dos membros contribuiu de alguma forma na realização deste trabalho, com cada um aprendi um pouco a ser um melhor pesquisador e uma melhor pessoa.Agradeço pelo agradável convívio que tivemos ao longo deste tempo e espero sinceramente que esta amizade ainda se mantenha por muito tempo.Finalmente, agradeço a minha família, em especial meus pais, Luiz e Bernadete, meu irmão, André, e minha noiva, Gisele, por estarem presentes em cada dificuldade, por me motivarem quando as dificuldades apareceram e por entenderem as noites em claro e os momentos de ausência familiar tão comuns na vida de um estudante/pesquisador.Devo o que sou à presença destes em minha vida.Agradeço também é claro, aos tios e primos que sempre estiveram na torcida e com quem compartilho momentos únicos, o que torna as dificuldades da vida menos significantes. RESUMOA descoberta do algoritmo de Shor, para a fatoração de inteiros em tempo polinomial, motivou esforços rumo a implementação de um computador quântico.Ele é capaz de quebrar os principais criptossistemas de chave pública usados hoje (RSA e baseados em curvas elípticas).Estes fornecem diversos serviços de segurança, tais como confidencialidade e integridade dos dados e autenticação da fonte, além de possibilitar a distribuição de uma chave simétrica de sessão.Para quebrar estes criptossistemas, um computador quântico grande (≈ 2000 qubits) é necessário.Todavia, alternativas começaram a ser investigadas.As primeiras respostas vieram da própria mecânica quântica.Apesar das propriedades interessantes encontradas na criptografia quântica, um criptossistema completo parece inatingível, principalmente devido as assinaturas digitais, essenciais para a autenticação.Foram então propostos criptossitemas baseadas em problemas puramente clássicos que (acredita-se) não são tratáveis por computadores quânticos, que são chamadas de pós-quânticas.Estes sistemas ainda sofrem da falta de praticidade, seja devido ao tamanho das chaves ou ao tempo de processamento.Dentre os criptossistemas pósquânticos, destacam-se o McEliece e o Niederreiter.Por si só, nenhum deles prevê assinaturas digitais, no entanto, as assinaturas CFS foram propostas, complementandoos.Ainda que computadores quânticos de propósito geral estejam longe de nossa realidade, é possível imaginar um circuito quântico pequeno e dedicado.A melhoria trazida por ele seria a diferença necessária para tornar essas assinaturas práticas em um cenário legitimamente pós-quântico.Neste trabalho, uma arquitetura híbrida quântica/clássica é proposta para acelerar algoritmos criptográficos pós-quânticos.Dois coprocessadores quânticos, implementando a busca de Grover, são propostos: um para auxiliar o processo de decodificação de códigos de Goppa, no contexto do criptossistema McEliece; outro para auxiliar na busca por síndromes decodificáveis, no contexto das assinaturas CFS.Os resultados mostram que em alguns casos, o uso de um coprocessador quântico permite ganhos de até 99, 7% no tamanho da chave e até 76, 2% em tempo de processamento.Por se tratar de um circuito específico, realizando uma função bem específica, é possível manter um tamanho compacto (≈ 300 qubits, dependendo do que é acelerado), mostrando adicionalmente que, caso computadores quânticos venham a existir, eles viabilizarão os criptossistemas pós-quânticos antes de quebrar os criptossistemas pré-quânticos.Adicionalmente, algumas tecnologias de implementação de computadores quânticos são estudadas, com especial enfoque na óptica linear e nas tecnologias baseadas em silício.Este estudo busca avaliar a viabilidade destas tecnologias como potenciais candidatas à construção de um computador quântico completo e de caráter pessoal.
A descoberta do algoritmo de Shor, para a fatoração de inteiros em tempo polinomial, motivou esforços rumo a implementação de um computador quântico. Ele é capaz de quebrar os principais criptossistemas de chave pública usados hoje (RSA e baseados em curvas elípticas). Estes fornecem diversos serviços de segurança, tais como confidencialidade e integridade dos dados e autenticação da fonte, além de possibilitar a distribuição de uma chave simétrica de sessão. Para quebrar estes criptossistemas, um computador quântico grande (2000 qubits) é necessário. Todavia, alternativas começaram a ser investigadas. As primeiras respostas vieram da própria mecânica quântica. Apesar das propriedades interessantes encontradas na criptografia quântica, um criptossistema completo parece inatingível, principalmente devido as assinaturas digitais, essenciais para a autenticação. Foram então propostos criptossitemas baseadas em problemas puramente clássicos que (acredita-se) não são tratáveis por computadores quânticos, que são chamadas de pós-quânticas. Estes sistemas ainda sofrem da falta de praticidade, seja devido ao tamanho das chaves ou ao tempo de processamento. Dentre os criptossistemas pós-quânticos, destacam-se o McEliece e o Niederreiter. Por si só, nenhum deles prevê assinaturas digitais, no entanto, as assinaturas CFS foram propostas, complementandos. Ainda que computadores quânticos de propósito geral estejam longe de nossa realidade, é possível imaginar um circuito quântico pequeno e dedicado. A melhoria trazida por ele seria a diferença necessária para tornar essas assinaturas práticas em um cenário legitimamente pós-quântico. Neste trabalho, uma arquitetura híbrida quântica/clássica é proposta para acelerar algoritmos criptográficos pós-quânticos. Dois coprocessadores quânticos, implementando a busca de Grover, são propostos: um para auxiliar o processo de decodificação de códigos de Goppa, no contexto do criptossistema McEliece; outro para auxiliar na busca por síndromes decodificáveis, no contexto das assinaturas CFS. Os resultados mostram que em alguns casos, o uso de um coprocessador quântico permite ganhos de até 99; 7% no tamanho da chave e até 76; 2% em tempo de processamento. Por se tratar de um circuito específico, realizando uma função bem específica, é possível manter um tamanho compacto (300 qubits, dependendo do que é acelerado), mostrando adicionalmente que, caso computadores quânticos venham a existir, eles viabilizarão os criptossistemas pós-quânticos antes de quebrar os criptossistemas pré-quânticos. Adicionalmente, algumas tecnologias de implementação de computadores quânticos são estudadas, com especial enfoque na óptica linear e nas tecnologias baseadas em silício. Este estudo busca avaliar a viabilidade destas tecnologias como potenciais candidatas à construção de um computador quântico completo e de caráter pessoal.