Aprendizado com Erros: O Problema Difícil

O problema de Aprendizagem com Erros (LWE) foi introduzido por Oded Regev em 2005 como fundamento da criptografia pós-quântica. Dada uma matriz aleatória A sobre Z_q e um vetor b = As + e, o objetivo é encontrar o vetor secreto s. O vetor e é um erro pequeno extraído de uma distribuição gaussiana discreta, tornando o problema computacionalmente intratável.

No problema LWE, A é uma matriz aleatória m x n amostrada uniformemente sobre Z_q, em que q é um módulo primo. O segredo s é um vetor n-dimensional, e e é um pequeno vetor de erro cujas entradas são extraídas de uma distribuição gaussiana estreita. Mesmo conhecendo a estrutura de A, um adversário não consegue distinguir b de um vetor aleatório uniforme.

Existem duas formulações padrão do LWE. O LWE de Busca solicita a recuperação do segredo s a partir de muitas amostras (A, b). O LWE de Decisão solicita distinguir amostras (A, As + e) de pares aleatórios uniformes (A, u). As duas formulações são equivalentes em tempo polinomial, o que significa que um algoritmo que resolve uma delas pode ser transformado para resolver a outra.

O termo de erro no LWE é extraído de uma distribuição gaussiana discreta sobre os inteiros, parametrizada pelo desvio padrão sigma. Valores pequenos de sigma garantem que e seja curto em comparação com q, fazendo b parecer quase igual a As mod q. Se sigma fosse zero, não haveria erro e o sistema poderia ser resolvido por eliminação gaussiana; portanto, o erro é essencial para a dificuldade do problema.

Regev provou uma redução notável: resolver amostras de LWE no caso médio é pelo menos tão difícil quanto resolver instâncias do pior caso do Problema do Vetor Mais Curto (SVP) em reticulados. Isso significa que, se conseguir quebrar o LWE com eficiência, conseguirá resolver qualquer problema de reticulados com eficiência. Não se conhece nenhum algoritmo clássico ou quântico que resolva o SVP do pior caso em tempo polinomial.

Ao contrário do RSA e da criptografia de curvas elípticas, não se conhece nenhum algoritmo quântico que ofereça uma aceleração exponencial contra o LWE. O algoritmo de Grover oferece no máximo uma aceleração quadrática, e os melhores algoritmos quânticos para reticulados, variantes do BKZ, não quebram o LWE quando são usados parâmetros adequadamente escolhidos. Isso faz do LWE uma base sólida para a segurança pós-quântica.

A segurança do LWE é determinada por três parâmetros: a dimensão n, que corresponde ao comprimento do segredo, o módulo q e o desvio padrão do erro sigma. Valores maiores de n e uma razão q/sigma menor aumentam a segurança. Para obter 128 bits de segurança pós-quântica, valores típicos são n = 1024, q em torno de 12289 e sigma em torno de 3,2. A ferramenta de estimativa de reticulados de Albrecht e colaboradores é usada para avaliar a segurança concreta.

O problema da Solução Inteira Curta (SIS) é uma hipótese relacionada sobre a dificuldade de reticulados, usada em assinaturas. Dada uma matriz aleatória A sobre Z_q, é preciso encontrar um vetor x curto e não nulo tal que Ax = 0 mod q. O SIS é a base de funções de resumo e esquemas de assinatura no contexto de reticulados, complementando o LWE, que fundamenta a criptografia e o encapsulamento de chaves.

Um esquema simples de criptografia LWE funciona da seguinte maneira: a chave pública é (A, b = As + e) e a chave privada é s. Para criptografar um bit m, o remetente calcula (u, v) = (A^T r, b^T r + m * floor(q/2)) para um vetor binário aleatório r. A descriptografia calcula v - s^T u e arredonda o resultado para recuperar m. Esse esquema alcança segurança IND-CPA sob a hipótese LWE.

O LWE possibilitou uma ampla variedade de construções criptográficas além da criptografia básica. Entre elas estão a criptografia totalmente homomórfica (FHE), a criptografia baseada em identidade (IBE), a criptografia baseada em atributos (ABE) e os protocolos de troca de chaves. CRYSTALS-Kyber, agora ML-KEM, padronizado como FIPS 203, é o esquema baseado em LWE mais utilizado na prática.

A criptografia baseada em LWE já está entrando em sistemas de produção. Google e Cloudflare realizaram experimentos com TLS usando Kyber entre 2018 e 2020. Chrome e Firefox adicionaram suporte a ML-KEM-768 em negociações híbridas de TLS em 2024. O Signal Protocol adicionou uma camada pós-quântica, PQXDH, usando ML-KEM-1024 para sigilo de encaminhamento, protegendo a confidencialidade de longo prazo das mensagens contra futuros computadores quânticos.

Qual afirmação descreve melhor a garantia de dificuldade do problema LWE?

O LWE é uma das hipóteses de dificuldade pós-quântica mais estudadas, respaldada por uma forte redução do pior caso a partir de problemas de reticulados. Seus três parâmetros, n, q e sigma, controlam o compromisso entre segurança e desempenho. O LWE resiste a ataques quânticos e fundamenta esquemas padronizados pelo NIST. Compreender o LWE é a porta de entrada para toda a criptografia moderna baseada em reticulados, incluindo ML-KEM e ML-DSA.