Fundamentos de Learning With Errors (LWE)

Aprendizado com Erros (LWE), de Regev (2005): dadas muitas equações lineares ruidosas sobre Z_q, encontre o vetor secreto s. O ruído e é pequeno, mas impede a eliminação gaussiana. Sem ruído, o sistema é fácil; mesmo com um ruído mínimo, ele se torna computacionalmente difícil.

Segredo s ∈ Z_q^n. O adversário recebe amostras (a_i, b_i), em que a_i ∈ Z_q^n é aleatório, b_i = + e_i mod q, e_i é um pequeno ruído proveniente da distribuição χ (por exemplo, gaussiana com σ = √n). A tarefa é encontrar s dadas um número polinomial de amostras.

Sem ruído: b_i = mod q. A eliminação gaussiana recupera s em O(n^3). Com ruído: até mesmo uma única equação incorreta compromete a eliminação. O ruído é pequeno o suficiente para permitir a descriptografia (usando a chave), mas grande o suficiente para impedir a criptoanálise.

Regev provou que o LWE pode ser reduzido a problemas de pior caso em reticulados (SIVP, GapSVP) por meio de uma redução quântica. Isso significa que, se o LWE for quebrado, muitos problemas difíceis em reticulados serão resolvidos — mas não se conhece nenhum algoritmo quântico para problemas em reticulados. O LWE oferece segurança pós-quântica.

O RLWE substitui Z_q^n pelo anel Z_q[x]/(f(x)), para um polinômio ciclotômico f. Uma amostra de RLWE codifica n equações — uma eficiência muito maior. O RLWE é a base do Kyber (KEM), do Dilithium (assinatura) e dos esquemas de HE BFV/BGV/CKKS.

A segurança depende de: n (dimensão, normalmente 512-2048), q (módulo, 1024-2^60), σ (desvio padrão do ruído). Um n maior e uma razão σ/q menor tornam o problema mais difícil. Os padrões pós-quânticos do NIST usam n=256 (dimensão do módulo) com k módulos (k=2,3,4).

Chave pública: (A, b=As+e). Para criptografar o bit m: escolha r aleatório e calcule o texto cifrado (u=A^T r, v = b^T r + m*q/2). Para descriptografar: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Arredonde para o m mais próximo. O ruído e mantém o texto cifrado ocultando m durante a criptografia.

LWE de decisão: distinguir (a, As+e) de (a, u), em que u é uniformemente aleatório. São computacionalmente indistinguíveis, supondo a dificuldade do LWE. Essa é a base da segurança semântica — para adversários sem a chave secreta, os textos cifrados parecem ruído aleatório.

Os melhores ataques conhecidos usam BKZ (redução de reticulados por blocos de Korkine-Zolotarev). Complexidade: subexponencial, mas não polinomial. BKZ-β requer 2^{0.292β} operações. Para LWE-512: segurança de aproximadamente 128 bits contra BKZ. Não se conhece nenhum ganho quântico de velocidade para BKZ.

O LWE modular (usado no Kyber) é RLWE sobre módulos de posto k. Ele oferece flexibilidade: k=2 para 512 bits de segurança, k=3 para 768 bits e k=4 para 1024 bits. A segurança e o desempenho aumentam conforme k. O NIST selecionou o Kyber (renomeado como ML-KEM) como padrão de PQC.

Segurança do RSA/ECC: baseada na fatoração de inteiros e no logaritmo discreto, vulneráveis a ataques quânticos por meio de Shor. Segurança do LWE: baseada em problemas de pior caso em reticulados, sem ganho quântico de velocidade conhecido. Tamanhos de chave: chaves LWE de aproximadamente 1 KB contra 256 bytes do RSA-2048. O LWE é maior, mas seguro contra ataques quânticos.

O que torna o LWE difícil de resolver mesmo com muitas amostras?

LWE: encontrar o segredo s a partir de equações lineares ruidosas — difícil até para computadores quânticos. O RLWE usa anéis de polinômios para obter eficiência. É a base do Kyber, do Dilithium e dos esquemas de HE. Próximo: os esquemas de HE BGV e BFV para operações com inteiros.