Ring-LWE e Reticulados de Módulos

O LWE padrão exige grandes produtos de matriz por vetor, o que resulta em chaves grandes. O LWE de Anel, introduzido por Lyubashevsky, Peikert e Regev em 2010, substitui vetores e matrizes por polinômios em um anel R_q = Z_q[X]/(f(X)). Esse ambiente estruturado permite chaves muito mais compactas e aritmética mais rápida, tornando o LWE de Anel a base prática da criptografia de reticulados no mundo real.

O polinômio f(X) usado no LWE de Anel normalmente é f(X) = X^n + 1, em que n é uma potência de 2. Esse é o polinômio ciclotômico de ordem 2n. Ele é escolhido porque é irredutível sobre Z, garante que o anel R_q tenha boas propriedades algébricas e permite a Transformada Teórica dos Números (NTT) para multiplicações eficientes. Os anéis ciclotômicos foram profundamente estudados e são considerados seguros.

No LWE de Anel, o segredo s é um polinômio em R_q, e as amostras têm a forma (a, b = a*s + e), em que a é um elemento aleatório uniforme do anel e e é um pequeno polinômio de erro. O adversário vê muitas amostras desse tipo e precisa recuperar s ou distingui-las de amostras uniformes. A dificuldade baseia-se na hipótese do LWE de Anel, que possui uma redução a partir de problemas do pior caso em reticulados ideais.

O LWE de Anel é mais difícil para um adversário, mas também vem com uma redução de segurança um pouco diferente da do LWE comum. A redução parte de problemas do pior caso em reticulados ideais, ideal-SVP, e não de reticulados arbitrários. Em princípio, a estrutura adicional dos reticulados ideais poderia torná-los mais fáceis do que os reticulados gerais, e essa é uma área ativa de pesquisa. Não se conhece nenhum ataque prático que explore essa estrutura.

O LWE Modular (M-LWE) generaliza tanto o LWE quanto o LWE de Anel ao trabalhar com uma matriz k x k de elementos do anel, em vez de um único elemento do anel ou de uma grande matriz de inteiros. Quando k = 1, ele se reduz ao LWE de Anel; à medida que k cresce, aproxima-se do LWE padrão. Esse parâmetro k ajustável permite equilibrar a confiança na segurança e o desempenho.

CRYSTALS-Kyber, agora ML-KEM, FIPS 203, baseia-se no LWE Modular com uma matriz de posto k sobre R_q. O parâmetro k controla diretamente o nível de segurança: k=2 busca 128 bits de segurança, ML-KEM-512; k=3 busca 192 bits, ML-KEM-768; e k=4 busca 256 bits, ML-KEM-1024. A estrutura modular permite uma única base de código, com a segurança ajustada pela alteração de k.

A multiplicação de polinômios em R_q = Z_q[X]/(X^n + 1) é o gargalo de desempenho. A Transformada Teórica dos Números (NTT) é uma transformada discreta de Fourier sobre Z_q que converte polinômios para a forma de avaliação, na qual a multiplicação se torna ponto a ponto. Quando q é escolhido de modo que a NTT possa ser aplicada, a multiplicação de polinômios leva tempo O(n log n), em vez de O(n^2), uma otimização essencial no ML-KEM e no ML-DSA.

A NTT exige que q seja primo e satisfaça q = 1 mod 2n, garantindo que Z_q contenha uma raiz 2n-ésima primitiva da unidade. Para ML-KEM com n = 256, q = 3329 satisfaz esse requisito. A NTT sobre Z_3329 é extremamente rápida em hardware moderno com instruções SIMD, permitindo milhares de operações de ML-KEM por segundo em processadores comuns.

O LWE em anel e o LWE modular reduzem drasticamente o tamanho das chaves em comparação com o LWE padrão. Uma chave pública LWE padrão para uma segurança de 128 bits pode ter 1 MB; o LWE em anel reduz esse tamanho para cerca de 800 bytes, e o LWE modular (ML-KEM-768) alcança uma chave pública de 1184 bytes com segurança pós-quântica de 192 bits. Essa compactação torna os esquemas baseados em reticulados práticos para TLS e sistemas incorporados.

Alguns criptógrafos temem que a estrutura algébrica adicional dos anéis ciclotômicos possa permitir ataques que não se aplicam ao LWE simples. Em 2024, Elias Rokicki e seus colaboradores publicaram uma análise do polinômio ciclotômico de ordem 2n, sem encontrar explorações práticas, mas destacando a importância de uma análise contínua. O processo de PQC do NIST considerou esse risco e escolheu o LWE modular em parte para reduzir a dependência de uma única estrutura de anel.

Além do Kyber, o LWE em anel fundamenta o CRYSTALS-Dilithium (ML-DSA), o esquema de assinaturas padronizado pelo NIST. A biblioteca SEAL, da Microsoft, permite a criptografia homomórfica por meio do LWE em anel. A biblioteca de criptografia Tink, do Google, inclui suporte a ML-KEM. O LWE em anel passou de uma construção teórica para uma implantação em produção em um período extraordinariamente curto, impulsionado pelo processo de padronização do NIST.

Qual é a principal vantagem do LWE em anel em relação ao LWE padrão?

O LWE em anel leva o LWE para o anel polinomial R_q = Z_q[X]/(X^n+1), reduzindo drasticamente o tamanho das chaves e permitindo aritmética rápida baseada em NTT. O LWE modular generaliza essa abordagem com uma estrutura de posto k, fundamentando o ML-KEM (FIPS 203) e o ML-DSA (FIPS 204). O primo q = 3329, adequado para NTT, permite uma implementação eficiente. A segurança baseia-se na dificuldade de problemas em reticulados ideais e modulares.