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.
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.
Em 1994, Peter Shor desenvolveu um algoritmo quântico para a fatorização de inteiros e para o problema do logaritmo discreto, fazendo de ambos RSA e ECC (Elliptic Curve Cryptography) facilmente quebráveis por computadores quânticos. Como se acredita que computadores quânticos irão fisicamente existir nos próximos poucos anos, quase toda a informação encriptada deixará de estar segura, e o impacto na vida prática das pessoas será no mínimo devastador. Aspetos como a comunicação entre pessoas, empresas e governos, operações bancárias, comércio eletrónico, passwords, entre muitos outros, estarão comprometidos. A criptografia de chave pública é hoje indispensável para indivíduos ou entidades comunicarem em segurança, logo, a existência de computadores quânticos constitui uma enorme ameaça para a nossa criptografia moderna. Caso computadores quânticos venham realmente a existir, substituir os atuais criptossistemas em uso vai ser algo necessário, uma vez que os criptossistemas resistentes a computadores quânticos em uso estão muito longe de ser suficientemente eficientes para serem postos em prática. É portanto imperativo estudar criptossistemas candidatos a substituir os atuais em termos da sua eficiência, praticidade e segurança contra ambos computadores clássicos e quânticos. Em 2016, o NIST, National Institute of Standards and Technology, instituto do Departamento do Comércio dos EUA, anunciou a sua busca por tais construções criptográficas resistentes a computadores quânticos. Estas devem ser eficientes e suficientemente boas para ser adotadas por um largo número de anos. Este instituto prevê a chegada de computadores quânticos para 2030, o que revela que existe pouco tempo para estudar as eventuais propostas de substituição aos criptossistemas atuais. Além disso, esta substituição demorará certamente o seu tempo, de maneira que se deve começar já a investir na busca de construções criptográficas resistentes a computadores quânticos. Desenvolvido por Jeffrey Hoffstein, Jill Pipher e Joseph Silverman (o mesmo Silverman famoso pelo seu trabalho em curvas elípticas) nos anos 90, apresentado na conferencia internacional de criptologia CRYPTO `96 e publicado em 1998, o criptossistema NTRU é um exemplo de um criptossistema resistente à computação quântica com potencial para vir a substituir os atuais criptossistemas clássicos em uso. Embora seja considerado um criptossistema baseado em reticulados, a sua descrição original não os usa, ainda que seja possível descrevê-lo inteiramente usando-os. Ainda assim, no artigo onde vem apresentado constam ataques baseados em reticulados que aproveitam certos aspetos que lhe são intrínsecos. A teoria por detrás do criptossistema NTRU é bastante simples, dado que se baseia em álgebra polinomial e na redução módulo dois inteiros primos entre si. O criptossistema NTRU é, portanto, muito fácil de ser compreendido, implementado, e de ser posto em prática: ambas as chaves pública e privada são rapidamente computáveis, tendo comprimento O(N), fazendo clara distinção com as chaves de comprimento O(N2) de outros criptossistemas ditos rápidos, tais como os criptossistemas McEliece e GGH, e encriptar e desencriptar com o criptossistema NTRU leva O(N2) operações, o que faz do mesmo consideravelmente mais rápido que o criptossistema RSA e a criptografia baseada em curvas elípticas. Além disto, o criptossistema NTRU é considerado como sendo um criptossistema probabilístico, uma vez que usa um elemento aleatório para encriptar uma mensagem. Desse modo, uma mensagem pode ter múltiplas encriptações possíveis. Desde a publicação do criptossistema NTRU, foram emitidos alguns relatórios técnicos, alguns consistindo em algoritmos que permitiram o criptossistema NTRU ganhar eficiência, outros descrevendo melhoramentos de ataques já existentes e também novos ataques e possíveis soluções para os contornar. A análise de segurança feita até hoje, incluindo por criptógrafos reconhecidos como Don Coppersmith, Johan Hastad, Andrew Odlyzho e Adi Shamir, deu ao criptossistema NTRU um estatuto de legitimidade e contribuiu para futura investigação, dado que o criptossistema NTRU se revelou interessante e promissor. Contudo, a análise realizada até hoje não implicou alterações profundas na estrutura do criptossistema NTRU, embora parâmetros mais largos tenham sido recomendados ao longo do tempo para alcançar os níveis de segurança desejados. Apesar de não ser acompanhado de uma prova de segurança, o criptossistema NTRU tem-se revelado seguro, uma vez que nenhum ataque quer clássico quer quântico com impacto significativo no criptossistema foi encontrado, o que revela que é uma boa alternativa aos criptossistemas clássicos em uso. O nosso estudo do criptossistema NTRU começou por explorar a página da companhia Security Innovation, onde se pode encontrar uma breve introdução à criptografia pós-quântica e um vídeo que explica o porquê da mesma ser estudada. Esta página contém um vasto número de recursos, incluindo tutoriais, surveys, relatórios técnicos, resumos e artigos, assim como uma vasta lista de artigos que escrutinam o criptossistema NTRU. De modo a aprofundar o estudo do criptossistema NTRU, explorámos e investigámos uma grande parte da documentação existente nesta página. Existe, como se pode constatar, uma quantidade tremenda de documentação para analisar, e devido a limitações no tempo optámos por estudar o criptossistema NTRUEncrypt, começando pelas suas raízes. Em 1997, Don Coppersmith e Adi Shamir fizeram a primeira análise de segurança ao criptossistema NTRU, em que descobriram que o método de ataque mais eficaz contra o criptossistema consistia em algoritmos de redução de reticulados com vista a encontrar vetores muito curtos numa classe particular de reticulados. Até à data, este é o método de ataque mais eficaz ao criptossistema NTRU. A segurança do criptossistema NTRU tem como base evidências empíricas, que mostra que encontrar vetores muito curtos num reticulado é um problema difícil, especialmente quando a dimensão do reticulado é muito grande. O estudo dos reticulados, denominado Geometria dos Números por Minkowski, data anteriormente das suas aplicações criptográficas e é uma área que contribuiu para o desenvolvimento de muitas outras, tais como a física, análise, álgebra e geometria. Este é um tópico bastante estudado, principalmente devido às aplicações dos algoritmos de redução de reticulados. Como a segurança do NTRU depende principalmente de ataques baseados em reticulados, criámos um capítulo inteiro dedicado aos reticulados e a algoritmos de redução de reticulados. Um importante avanço nesta área foi o algoritmo LLL (por vezes chamado algoritmo L3) de Lenstra, Lenstra e Lovász em 1982, desenvolvido antes dos reticulados serem considerados relevantes em criptografia. Este algoritmo permite encontrar um vetor moderadamente curto num reticulado em tempo polinomial. Com o passar do tempo, este algoritmo foi melhorado, dando origem ao algoritmo BKZ (Blockwise-Korkine-Zolotarev), que é até hoje na prática o melhor algoritmo de redução de reticulados permitindo encontrar vetores muito curtos em reticulados. Este algoritmo deve-se a Schnorr (1987), no entanto não é executado em tempo polinomial. Portanto, encontrar vetores muito curtos num reticulado de larga dimensão continua a ser um problema em aberto. Em 2011, Yuanmi Chen e Phong Q. Nguyen criaram um algoritmo que permite simular o algoritmo BKZ, denominado BKZ simulation algorithm, podendo prever aproximadamente o output e o tempo de execução do algoritmo BKZ. Este trabalho foi dividido em três partes. A primeira é uma pequena introdução à computação quântica, principalmente aos básicos da mecânica quântica e à Transformada de Fourier, uma vez que alguns leitores poderão não conhecer estes conteúdos. Além disso, algumas noções de computação quântica são mencionadas neste trabalho, pelo que faz todo o sentido incluir uma breve referência às mesmas. A segunda parte trata de reticulados em geral, apresenta os algoritmos de redução de reticulados LLL e BKZ (juntamente com o BKZ simulation algorithm) e também alguns exemplos de criptossistemas de chave pública que se baseiam em reticulados. A terceira parte revela uma análise do criptossistema NTRU, focando-se principalmente em ataques baseados em reticulados, que são os que de longe melhor se aplicam aos reticulados associados ao criptossistema NTRU. Como perspetiva de trabalho futuro, apresenta-se uma ideia de um algoritmo quântico para a redução de reticulados.
Oblivious Transfer é um dos blocos de construção mais importantes em criptografia e útil para a construção de protocolos seguros. Com o advento da computação quântica houve um impulso na pesquisa e desenvolvimento de protocolos criptográficos resistentes ao processamento quântico de computadores. Assim, em 2018, o protocolo SIOT (Supersingu- lar Isogeny Oblivious Transfer) foi apresentado como o primeiro esquema OT criptográfico pós-quântico baseado em isogenias de curvas elípticas supersingulares. Inicialmente, elaborou-se um esquema de OT combinado com as primitivas criptográficas do protocolo SIDH(Supersingular Isogeny Diffie-Hellman). Além disso, o protocolo SIOT foi construído na sua configuração mais simples contra adversários semi-honestos. No entanto, o mesmo foi submetido a escrutínios que resultaram na necessidade de desenvolver novas provas de segurança. Quase em paralelo, surgiram novos e eficientes ataques criptoanalíticos ao protocolo SIDH que consequentemente comprometeram a estrutura de segurança do SIOT. Desta forma, em um primeiro momento, as novas definições de provas de segurança englobaram a compatibilização de determinados parâmetros da funcionalidade OT do próprio protocolo SIOT com hipóteses de segurança de problemas computacionais de isogenias. Após isso, foram analisadas e implementadas as contramedidas de segurança do protocolo M-SIDH (Masked-Supersingular Isogeny Diffie-Hellman). Portanto, propõem-se um protocolo OT baseado em isogenias de curvas elípticas e com resistência a ataques quânticos, em uma forma simples.
0 algoritmo de Shor e a evolução da computação quântica trouxeram grandes ameaças à segurança dos criptossistemas atuais. Pela necessidade de se encontrar novas alternativas, surgiu a criptografia pós-quântica. Esta dissertação pode ser dividida em três partes principais. Na primeira apresentamos alguns elementos de teoria dos números e descrevemos um criptossistema clássico, o RSA, cuja segurança pode ser facilmente quebrada recorrendo a ataques quânticos. Na segunda parte descrevemos a implementação do algoritmo de Shor, que é um ataque a esse e a todos os criptossistemas cuja segurança reside no problema da fatorização ou no problema do logaritmo discreto. Na implementação deste algoritmo minimizámos o número de qubits necessários. Para isso, utilizámos transformadas de Fourier quânticas para realizar operações como a adição, a multiplicação e a exponenciação modular. Assim, segundo a nossa abordagem, precisámos de apenas Li + 2L2 + 3 qubits, para implementar o algoritmo de Shor, ou seja, para encontrar o período da função /(x) = ax mod N, onde Li corresponde ao número de qubits necessários para representar x tal que N2 < 2L1 < 2N2 e L2 corresponde ao número de qubits necessários para representar N. Por fim, na última parte desta dissertação, apresentaremos elementos da criptografia pós-quântica, em particular, um protocolo proposto por nós. Este é uma nova variante do criptossistema de McEliece, no qual se propõe o uso de códigos convolucionais em vez do uso de códigos de bloco. Assim, a parte codificadora da nossa chave pública, que denotaremos por G'(D), será ela própria convolucional. Ao estudarmos várias possibilidades de ataques para este criptossistema, verificámos que, em comparação com as restantes variantes, para uma chave pública menor conseguimos ter um fator de trabalho muito maior, o que se traduz numa maior segurança
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.
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.
Resumo A física quântica marca um novo paradigma no desenvolvimento de tecnologias – nesse contexto, este trabalho apresenta um panorama acerca da Distribuição Quântica de Chaves (QKD). Partindo dos conceitos clássicos de criptografia e da ameaça iminente de computadores quânticos capazes de quebrar algoritmos de segurança amplamente utilizados, como o RSA, exploramos como a QKD aproveita propriedades intrínsecas da mecânica quântica – superposição, medidas em bases conjugadas e emaranhamento – para gerar chaves criptográficas seguras. Discutimos os primeiros protocolos com modelagem discreta (BB84, E91) detalhando cada etapa de pós-processamento: estimação de parâmetros, correção de erros e amplificação de privacidade; além de elaborarmos sobre as noções básicas de como avaliar segurança nesse contexto. Abordamos também técnicas modernas, como QKD em variáveis contínuas e (semi-)independente de dispositivos, que apresentam algumas vantagens frente às técnicas tradicionais. Com uma linguagem acessível e exemplos práticos, este tutorial convida o leitor a mergulhar na criptografia quântica e dar os primeiros passos para compreender a área de Distribuição Quântica de Chaves. Dessa forma, visamos fomentar a formação de uma nova geração de pesquisadores nesta área, dada as crescentes iniciativas de redes quânticas em desenvolvimento no Brasil.