Célebre algoritmo de criptografia recebe atualização | Revista Quanta

Nas nossas vidas cada vez mais digitais, a segurança depende da criptografia. Envie uma mensagem privada ou pague uma conta online e você estará contando com algoritmos projetados para manter seus dados em segredo. Naturalmente, algumas pessoas querem descobrir esses segredos – por isso os investigadores trabalham para testar a força destes sistemas para garantir que não desmoronarão nas mãos de um atacante inteligente.

Uma ferramenta importante neste trabalho é o algoritmo LLL, nomeado em homenagem aos pesquisadores que publicou em 1982 — Arjen Lenstra, Hendrik Lenstra Jr. e László Lovász. A LLL, juntamente com seus muitos descendentes, pode quebrar esquemas criptográficos em alguns casos; estudar como eles se comportam ajuda os pesquisadores a projetar sistemas menos vulneráveis ​​a ataques. E os talentos do algoritmo vão além da criptografia: é também uma ferramenta útil em áreas matemáticas avançadas, como a teoria computacional dos números.

Ao longo dos anos, os pesquisadores aprimoraram variantes da LLL para tornar a abordagem mais prática – mas apenas até certo ponto. Agora, dois criptógrafos construíram um novo algoritmo no estilo LLL com um aumento significativo na eficiência. A nova técnica, que conquistou o Prêmio de melhor artigo no Conferência Internacional de Criptologia 2023, amplia a gama de cenários em que cientistas da computação e matemáticos podem usar abordagens semelhantes às da LLL.

“Foi realmente emocionante”, disse Chris Peikert, um criptógrafo da Universidade de Michigan que não esteve envolvido no artigo. A ferramenta tem sido foco de estudo há décadas, disse ele. “É sempre bom quando um alvo que vem sendo trabalhado há tanto tempo… mostra que ainda há surpresas a serem encontradas.”

Algoritmos do tipo LLL operam no mundo das redes: coleções infinitas de pontos regularmente espaçados. Como forma de visualizar isso, imagine que você está pavimentando o chão. Você poderia cobri-lo com ladrilhos quadrados, e os cantos desses ladrilhos formariam uma treliça. Alternativamente, você pode escolher um formato de bloco diferente – digamos, um paralelogramo longo – para criar uma rede diferente.

Uma rede pode ser descrita usando sua “base”. Este é um conjunto de vetores (essencialmente, listas de números) que você pode combinar de diferentes maneiras para obter todos os pontos da rede. Vamos imaginar uma rede com base composta por dois vetores: [3, 2] e [1, 4]. A rede são apenas todos os pontos que você pode alcançar adicionando e subtraindo cópias desses vetores.

Esse par de vetores não é a única base da rede. Toda rede com pelo menos duas dimensões tem infinitas bases possíveis. Mas nem todas as bases são criadas iguais. Uma base cujos vetores são mais curtos e mais próximos de ângulos retos entre si é geralmente mais fácil de trabalhar e mais útil para resolver alguns problemas computacionais, por isso os pesquisadores chamam essas bases de “boas”. Um exemplo disso é o par de vetores azuis na figura abaixo. Bases que consistem em vetores mais longos e menos ortogonais — como os vetores vermelhos — podem ser consideradas “ruins”.

Este é um trabalho para a LLL: dar a ela (ou a seus irmãos) uma base de uma rede multidimensional, e ela produzirá uma melhor. Este processo é conhecido como redução da base da rede.

O que tudo isso tem a ver com criptografia? Acontece que a tarefa de quebrar um sistema criptográfico pode, em alguns casos, ser reformulada como outro problema: encontrar um vetor relativamente curto em uma rede. E às vezes, esse vetor pode ser extraído da base reduzida gerada por um algoritmo estilo LLL. Esta estratégia ajudou os investigadores a derrubar sistemas que, à primeira vista, parecem ter pouco a ver com redes.

Num sentido teórico, o algoritmo LLL original é executado rapidamente: o tempo que leva para ser executado não aumenta exponencialmente com o tamanho da entrada - isto é, a dimensão da rede e o tamanho (em bits) dos números no vetores de base. Mas aumenta como uma função polinomial, e “se você realmente quiser fazer isso, o tempo polinomial nem sempre é tão viável”, disse Léo Ducas, criptógrafo do instituto nacional de pesquisa CWI, na Holanda.

Na prática, isso significa que o algoritmo LLL original não consegue lidar com entradas muito grandes. “Matemáticos e criptógrafos queriam a capacidade de fazer mais”, disse Keegan Ryan, estudante de doutorado na Universidade da Califórnia, San Diego. Os pesquisadores trabalharam para otimizar algoritmos no estilo LLL para acomodar entradas maiores, muitas vezes alcançando bom desempenho. Ainda assim, algumas tarefas permaneceram teimosamente fora de alcance.

O novo artigo, de autoria de Ryan e seu consultor, Nadia Heninger, combina múltiplas estratégias para melhorar a eficiência de seu algoritmo estilo LLL. Por um lado, a técnica utiliza uma estrutura recursiva que divide a tarefa em partes menores. Por outro lado, o algoritmo gerencia cuidadosamente a precisão dos números envolvidos, encontrando um equilíbrio entre velocidade e resultado correto. O novo trabalho viabiliza aos pesquisadores a redução de bases de reticulados com milhares de dimensões.

Trabalhos anteriores seguiram uma abordagem semelhante: Um papel 2021 também combina recursão e gerenciamento de precisão para agilizar o trabalho de redes grandes, mas funcionou apenas para tipos específicos de redes, e não para todas aquelas que são importantes em criptografia. O novo algoritmo se comporta bem em uma faixa muito mais ampla. “Estou muito feliz que alguém tenha feito isso”, disse Thomas Espitau, pesquisador de criptografia da empresa PQShield e autor da versão 2021. O trabalho de sua equipe ofereceu uma “prova de conceito”, disse ele; o novo resultado mostra que “você pode fazer uma redução muito rápida da rede de maneira sólida”.

A nova técnica já começou a se mostrar útil. Página Aurel, um matemático do instituto nacional de pesquisa francês Inria, disse que ele e sua equipe colocaram uma adaptação do algoritmo para funcionar em algumas tarefas computacionais da teoria dos números.

Algoritmos do tipo LLL também podem desempenhar um papel na pesquisa relacionada a sistemas de criptografia baseados em rede projetados para permaneça seguro mesmo em um futuro com computadores quânticos poderosos. Eles não representam uma ameaça para esses sistemas, uma vez que derrubá-los exige encontrar vetores mais curtos do que esses algoritmos podem alcançar. Mas os melhores ataques que os pesquisadores conhecem usam um algoritmo estilo LLL como um “bloco de construção básico”, disse Wessel van Woerden, criptógrafo da Universidade de Bordeaux. Em experimentos práticos para estudar esses ataques, esse alicerce pode desacelerar tudo. Usando a nova ferramenta, os pesquisadores poderão expandir a gama de experimentos que podem executar nos algoritmos de ataque, oferecendo uma imagem mais clara de seu desempenho.

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de ciência da computação e você estará inscrito para ganhar de graça Quanta mercadoria.