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.
Em um sentido teórico, o algoritmo LLL original é executado rapidamente: o tempo que leva para ser executado não é escalonado 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 artigo de 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 Aurelum 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 tais 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.
História original reimpresso com permissão de Revista Quanta, uma publicação editorialmente independente do Fundação Simons cuja missão é melhorar a compreensão pública da ciência, cobrindo desenvolvimentos e tendências de pesquisa em matemática e ciências físicas e biológicas.
