Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Post-quantum cryptography: lattice-based cryptography and analysis of NTRU public-key cryptosystem

Rafael Torrado Monteiro

Published Jan 1, 2016• 1 citation
OpenAlex

Abstract

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.

Related papers

Ataques quânticos e os criptossistemas de McEliece

Jorge Manuel Tavares Brandão

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

•Jul 31, 2018•0 citations

O algoritmo polinomial de Shor para fatoração em um computador quântico

Mário Sansuke Maranhão Watanabe

Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas

•Jan 1, 2003•0 citations

UM ESTUDO EXPLORATÓRIO DAS FALHAS DE SEGURANÇA DE ALGORITMOS DE CRIPTOGRAFIA NA ERA DA COMPUTAÇÃO QUÂNTICA

Rodrigo P. Pasquale, Calebe P. Bianchini

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.

•Dec 21, 2020•1 citation

Geometria Elíptica e a Defesa Criptográfica Pós-Quântica

PAULO SÉRGIO DE ANDRADE

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.

•Nov 6, 2025•0 citations

Aceleração de algoritmos baseados em treliças para criptossistemas pós-quânticos

Filipe António Emílio Cabeleira

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.

•Feb 28, 2019•0 citations

Esquemas de assinatura digital Lattice-based e experimentação de certificados híbridos com criptografia pós-quântica

Maria Zita Fiqueli de Abreu

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.

•Jan 1, 2020•0 citations
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.
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
Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas
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.
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.