Lance Fortnow escreve sobre complexidade computacional em seu blog há mais de duas décadas e não é de se exaltar. O post dele sobre a nova alegação terminou com uma frase cautelosa: "Eu mesmo não verifiquei a prova, mas agora é seguro assumir que a hipótese do tempo exponencial já era" (Computational Complexity).
A alegação vem de dois laboratórios. A OpenAI, empresa por trás do ChatGPT, diz que seu modelo refutou a Hipótese do Tempo Exponencial, normalmente abreviada como ETH. Horas depois, a Anthropic, criadora do Claude (os dois assistentes são comparados aqui), publicou a própria refutação. As manchetes então ligaram a notícia a uma briga entre matemáticos e a temores pela criptografia global. Lemos os textos dos dois laboratórios, os comentários de especialistas e a cobertura da imprensa, e nossa conclusão é direta: o resultado provavelmente é real e importante para os teóricos, e não é motivo para mudar a forma como você protege seus dados. Duas das três manchetes tratam de disputas diferentes, e a terceira fala de uma tendência.
O que é a Hipótese do Tempo Exponencial, em termos simples?
Comece por um quebra-cabeça chamado 3-SAT. Você recebe uma longa lista de condições sobre n chaves de verdadeiro ou falso, cada condição no formato "A, ou não B, ou C", e precisa encontrar uma configuração das chaves que satisfaça todas elas. Conferir uma configuração proposta é rápido. Encontrar uma é a parte difícil, como num Sudoku: um tabuleiro preenchido é fácil de verificar, e um em branco não é.
A ETH, proposta em 1999 por Russell Impagliazzo e Ramamohan Paturi (com Francis Zane), afirma que todo algoritmo para 3-SAT precisa de um tempo que cresce como 2 elevado a c vezes n, para alguma constante c maior que zero (Fortnow). Imagine um cadeado de combinação em que cada disco extra multiplica o trabalho por um fator fixo, digamos 1,3. A ETH diz que esse fator pode ser reduzido, mas nunca chegar a 1.
A refutação diz que o fator de fato diminui em direção a 1 conforme as fórmulas crescem. O artigo da OpenAI apresenta, segundo Fortnow, um tempo de execução de cerca de 2 elevado a n vezes log log n sobre a raiz quadrada de log n. Isso ainda está longe de ser rápido. Só cresce mais devagar do que qualquer multiplicador fixo. O texto da própria Anthropic é franco quanto a isso: "O resultado é puramente assintótico e não diz nada sobre resolver fórmulas na prática" (Anthropic).
Por que os teóricos deram tanta importância? A ETH foi usada em centenas de artigos como substituta de "este problema não pode ser resolvido muito mais rápido" (OpenAI). Se a hipótese é falsa, esses argumentos de dificuldade precisam ser reavaliados, embora Fortnow observe que "o fato de a ETH e a SETH falharem não significa que suas implicações sejam falsas."
Verificou-se mais do que o normal, e menos do que o necessário para dar o caso por encerrado
A checagem até agora é maior do que a maioria dos avanços recebe na primeira semana. A OpenAI diz que seu modelo encontrou a refutação dez dias antes do anúncio e que ela foi formalizada em Lean, um verificador de provas que só aceita passos que consegue conferir (OpenAI). A Anthropic diz que um modelo Claude interno encontrou a versão dela, e que os arquivos em Lean foram escritos por modelos de IA (Anthropic).
Desde então, humanos entraram na jogada. Ryan O'Donnell, da Carnegie Mellon, publicou uma exposição reescrita da prova, e Fortnow diz que Shiva Kintali publicou outra, ambas buscando simplicidade em vez dos melhores limites. Timothy Gowers disse que é "Muito surpreendente e de grande consequência que ela seja falsa" (Business Insider).
Quem foi formalmente designado para checar a prova são Impagliazzo, Paturi e Ryan Williams, do MIT, que disse ao TechCrunch que partes da prova são rotineiras, mas que "há duas ou três partes com cara de alienígena". A Business Insider informa que Williams não certificou o resultado e que o grupo afirma que sua participação não é um aval. Mais um alerta, vindo do repositório da própria Anthropic: o Lean verifica as provas, mas "nenhuma máquina confere se este arquivo diz o que o artigo diz", então uma pessoa precisa ler o curto arquivo de enunciados. Eles o mantiveram curto por esse motivo.
Nossa leitura: uma alegação de dois laboratórios, com provas verificadas por máquina e reescritas humanas em poucos dias, é um sinal incomumente forte. Ainda assim, é uma alegação até que o grupo de especialistas e uma revista científica digam o contrário.
A briga dos matemáticos é sobre este resultado?
Na maior parte, não. A "briga entre matemáticos" da BBC trata de outro problema. A reportagem cobre a disputa em torno de Navier-Stokes, em que Tristan Buckmaster, da NYU, perguntou se seus rascunhos, armazenados na ferramenta Codex da OpenAI, poderiam ter alimentado o trabalho da própria OpenAI. A OpenAI disse que ninguém lá viu o trabalho da outra equipe e que os prompts dele "não poderiam ter influenciado o sistema de forma alguma".
A manchete "passou na frente" da Scientific American é sobre Yang-Mills, um problema de física. A revista diz que a OpenAI parece ter chegado antes de Ethan Sussman, que trabalha com Levent Alpöge, da Anthropic, a uma prova. Alpöge protestou no X. Nada disso diz respeito a o algoritmo de 3-SAT funcionar ou não.
A querela da ETH é sobre processo. Williams chamou um lançamento anterior da OpenAI de "um ataque DDOS contra matemáticos" (X), e depois concordou em ajudar neste. A Scientific American diz que a abordagem da OpenAI em dois dos três resultados violou um esclarecimento do próprio grupo consultivo de especialistas em IA e matemática da empresa, e que os prompts e a cadeia de raciocínio por trás deles continuam privados. No caso da ETH, a OpenAI concordou em publicar a prova e financiar uma conferência.
Isso quebra o RSA ou a criptografia do meu celular?
Não, e não por esse caminho. Dizemos isso de forma tão categórica porque os motivos são específicos. Primeiro, o algoritmo resolve k-SAT. Fortnow enfatiza que ele "não traz nada de novo para Subset Sum ou Caixeiro Viajante", porque converter esses problemas em 3-SAT infla demais o número de variáveis. Segundo, o RSA se baseia na dificuldade de decompor um número enorme em dois primos (o Financial Times descreve o método sem citar o nome), que é um problema diferente de satisfazer fórmulas lógicas, e nenhuma das fontes que lemos diz que o novo algoritmo chegue a ele. Terceiro, o limite é assintótico: nada muda para uma chave de 2.048 bits em nenhuma máquina que exista.
Williams levantou a preocupação óbvia com o responsável científico da OpenAI, Dan Roberts. Segundo o TechCrunch, ele perguntou se algo havia se tornado inseguro e relatou que, aparentemente, a OpenAI tinha verificado e estava "razoavelmente confiante" de que não havia quebras implicadas. Essa informação é de segunda mão e não foi publicada, então pese-a de acordo. Williams também disse que um algoritmo melhorado poderia implicar que alguns tamanhos de chave passem a ser considerados quebrados.
Há uma questão em aberto de verdade por baixo disso. Williams diz que "todo cientista da computação provavelmente deveria dar um pouco mais de peso à plausibilidade de P = NP", mas John D. Cook ressalta que "o status de P = NP ainda é desconhecido" (Business Insider). Williams também não acha que o novo algoritmo seja o melhor possível. Se surgir um mais afiado, os argumentos mudam.
A matéria do Financial Times é sobre uma tendência, não sobre esta prova
O artigo do FT trata da crescente capacidade matemática da IA e da criptografia em geral, e no texto que conseguimos ler ele nunca menciona a ETH. As fontes são comedidas. O matemático australiano Geordie Williamson disse a uma plateia do Imperial College que a IA está causando "uma reestruturação completa do que é dificuldade" e que devemos esperar choques. Daniel Shiu, da Universidade de Manchester, chamou a quebra de criptografia por IA de "risco significativo" para "formas mais matemáticas de criptografia", citando alguns dos algoritmos resistentes a computação quântica "menos maduros". O próprio FT diz que a IA "ainda não quebrou nenhum método central de criptografia".
Scott Aaronson acrescentou uma ponta solta: a criptografia está notavelmente ausente da lista anterior de 376 artigos da OpenAI, e, numa atualização de seu post, ele escreveu que suas fontes dizem que empresas de IA começaram a investigar se seus modelos conseguem quebrar protocolos. Ele não deu nomes, e nós também não podemos dar.
Nossa leitura: a preocupação razoável é com os esquemas mais novos, não com os que rodam no seu navegador. Os padrões do NIST de 2024 incluem dois esquemas baseados em reticulados e um terceiro padrão de assinatura construído sobre um tipo diferente de matemática, mantido como reserva caso o primeiro se mostre vulnerável.
O que uma pequena empresa deve fazer de fato
Quase nada, e nada urgente. A árvore abaixo organiza as três situações que consideramos relevantes.
Vale adotar um hábito independentemente desta história. O regulador do Reino Unido disse ao FT que as empresas "não devem esperar para agir" na preparação contra riscos de IA e de computação quântica para a criptografia, e a BT disse querer que sua criptografia seja "trocada com mais facilidade conforme padrões, tecnologias e ameaças evoluem". Para um pequeno negócio, isso se traduz em manter o software atualizado e perguntar aos fornecedores como eles trocariam de algoritmo. Nosso framework para confiar seus dados a ferramentas de IA cobre as perguntas a fazer aos fornecedores, e o ranking de Segurança e Privacidade do ToolRank lista ferramentas por categoria.
Três coisas para acompanhar antes de alguém dar o caso por encerrado
Fique de olho em três coisas. O relatório do grupo de especialistas formado por Impagliazzo, Paturi e Williams, e a conferência que a OpenAI concordou em financiar. Leituras independentes dos arquivos de enunciados em Lean, já que é ali que um erro sutil poderia se esconder. E a revisão por pares em revista científica, da qual ainda não encontramos sinal. Até que o primeiro desses itens apareça, diríamos "muito provavelmente refutada".