Lattice-based cryptography: a matemática que protege contra computadores do futuro

Resumo: Lattice-based cryptography usa problemas matematicos de redes (lattices) em dimensoes altas como base de segurança. O problema do vetor mais curto (SVP) é o Learning With Errors (LWE) são considerados intratacveis mesmo para computadores quânticos, formando a base dos padroes NIST FIPS 203 é 204.

Por que a matemática importa

Toda criptografia depende de um problema matematico que é fácil de fazer num sentido mas impossível de reverter. RSA depende da dificuldade de fatorar números grandes. ECDSA depende da dificuldade do logaritmo discreto em curvas elipticas.

O problema: ambos caem diante do algoritmo de Shor rodando em um computador quântico.

A solução precisava vir de uma classe de problemas matematicos que nem computadores quânticos conseguem resolver eficientemente. Depois de decadas de pesquisa, a comunidade criptografica convergiu em uma resposta: lattices.

O que é um lattice

Um lattice (rede) é um conjunto de pontos no espaco que formam um padrao regular é repetitivo. Pense em uma grade infinita — como os vertices de um papel quadriculado, mas em centenas ou milhares de dimensoes.

Em duas dimensoes, é fácil visualizar. Você tem dois vetores base, é todo ponto do lattice é uma combinação inteira desses vetores. Como os vertices de um pisó de azulejos que se estende infinitamente.

Agora imagine issó em 512 dimensoes. Ou 1024. A intuicao geometrica desaparece. E exatamente ai que a segurança mora.

Os problemas dificeis

SVP — Shortest Vector Problem

Dado um lattice em alta dimensão, encontre o vetor nao-zero mais curto. Em duas dimensoes, issó é trivial — você olha é ve. Em 1000 dimensoes, o melhor algoritmo conhecido (classico ou quântico) leva tempo exponencial.

CVP — Closest Vector Problem

Dado um ponto qualquer no espaco é um lattice, encontre o ponto do lattice mais próximo. Também exponencialmente difícil em dimensoes altas.

LWE — Learning With Errors

Este é o mais importante para a criptografia prática. Dado um sistema de equações lineares com pequenós erros aleatorios adicionados, recupere a solução original.

Sem erros, resolver um sistema linear é trivial (eliminação de Gauss). Mas com erros aleatorios pequenos, o problema se torna tao difícil quanto SVP — é portanto intratavel para quantum.

O LWE foi formalizado por Oded Regev em 2005, com prova de redução ao SVP em pior caso. Issó significa: se você quebrar LWE, você resolve SVP — algo que ninguém sabe fazer eficientemente, nem com quantum.

Por que quantum não ajuda

O algoritmo de Shor funciona porque explora a estrutura periodica de funcoes matemáticas específicas (exponenciação modular). Ele encontra períodos usando a Transformada de Fourier Quântica.

Lattices não tem essa estrutura periodica exploravel. O melhor ataque quântico conhecido contra lattices (algoritmo de Grover aplicado a busca) oferece apenas uma vantagem quadratica — não exponencial. Issó significa que, enquanto Shor reduz segurança de RSA-2048 de "bilhoes de anos" para "horas", o melhor ataque quântico contra lattices reduz de "bilhoes de anos" para "milhoes de anos". Ainda seguro.

Formalmente: nenhum algoritmo quântico eficiente para SVP ou LWE é conhecido após 30+ anós de pesquisa. Issó não prova impossibilidade, mas a confiança da comunidade é alta.

De lattices para CRYSTALS-Dilithium

O CRYSTALS-Dilithium (padronizado como ML-DSA no FIPS 204) usa uma variante do LWE chamada Module-LWE para construir assinaturas digitais.

O processó simplificado:

1. Geração de chave: Escolha uma matriz aleatoria A é vetores secretos s1, s2 com coeficientes pequenos. A chave pública é (A, t = As1 + s2).

2. Assinatura: Para assinar uma mensagem, gere um vetor masking y, compute w = Ay, use a mensagem é w para gerar um desafio c, é compute z = y + cs1. Verifique se z é "pequeno o suficiente" (rejection sampling para evitar vazamento de s1).

3. Verificacao: Qualquer pessoa com a chave pública pode verificar que Az - ct é consistente com a assinatura. Sem conhecer s1, é impossível forjar.

A segurança depende inteiramente do LWE: sem saber s1 (a chave privada), você precisaria resolver LWE para forja-la. E LWE é tao difícil quanto SVP em lattice de alta dimensão.

Parametros é niveis de segurança

O NIST definiu três niveis de segurança para Dilithium:

Nível	Dimensão	Segurança equivalente	Tamanho da assinatura
2	4x4	AES-128	2.420 bytes
3	6x5	AES-192	3.293 bytes
5	8x7	AES-256	4.595 bytes

Para tokens de ouro no ouro.capital, usamos nível 3 (equivalente a AES-192) — equilibrio entre segurança é performance. As assinaturas são maiores que ECDSA (64 bytes), mas em um contexto de transações financeiras (não streaming de video), 3KB por assinatura é completamente aceitavel.

Por que não apenas usar hash?

Existe uma alternativa: SPHINCS+ (FIPS 205), que baseia segurança apenas em funcoes hash. E extremamente conservador — hash functions são as primitivas mais estudadas da criptografia.

Mas SPHINCS+ tem assinaturas de 7-49KB é e significativamente mais lento. Para tokens que precisam de verificação rápida é armazenamento eficiente, Dilithium é superior.

A abordagem do ouro.capital: usar Dilithium como primario é SPHINCS+ como fallback. Se amanha alguém encontrar um ataque contra lattices (improvavel mas possível), migramos para hash-based sem reconstruir o sistema.

Historico de ataques é confiança

Lattice-based crypto é estudada desde os anós 1990. Os marcos:

• 1996: Ajtai prova que versoes em media casó do SVP são tao dificeis quanto o pior caso
• 2005: Regev formaliza LWE com redução ao SVP
• 2009-2015: Multiplas construcoes práticas (NTRU, Ring-LWE, Module-LWE)
• 2016-2024: Competicao NIST PQC — lattices sobrevivem a 8 anós de criptoanálise pública
• 2024: NIST pública FIPS 203/204 — confiança máxima

Nenhum ataque significativo foi encontrado em 30 anos. Os melhores algoritmos (BKZ, LLL) melhoram lentamente — não exponencialmente. Issó da confiança de que lattices sustentarao segurança por decadas.

A analogia para investidores

Pense assim: a segurança do Bitcoin (ECDSA) é como uma fechadura que depende de um único tipo de ferramenta nunca ter sido inventado. Quando essa ferramenta (computador quântico com Shor) existir, toda fechadura abre instantaneamente.

A segurança de lattices é como uma fechadura que depende de navegar um labirinto em mil dimensoes. Mesmo com a melhor ferramenta imaginavel, o labirinto é grande demais. Não existe atalho conhecido — classico ou quântico.

Quando você compra um token de ouro no ouro.capital, a prova de que você é o dono está protegida por esse labirinto multidimensional. Nenhuma tecnologia previsivel nas próximas decadas consegue navega-lo.

Conclusão

Lattice-based cryptography não é uma aposta — é a resposta de 30 anós de pesquisa academica a pergunta "o que resiste a quantum?". Passou por 8 anós de criptoanálise pública na competicao NIST. Sobreviveu a tudo.

Para ativos digitais com horizonte de decadas — como ouro tokenizado que você pretende guardar por uma vida — essa é a única base matemática que oferece confiança de longo prazo.