Parte IV · 2 — As novas famílias
Se Shor quebra fatoração e logaritmo discreto, a saída é fundar a assimetria em problemas que o quântico não sabe resolver. Após anos de competição pública, a NIST padronizou os vencedores em 2024 — quase todos baseados em reticulados.
2.1 A ideia: novos problemas difíceis
Criptografia pós-quântica (PQC) não usa computadores quânticos — roda em hardware clássico comum. O que muda é o problema difícil sob a primitiva. Buscam-se problemas difíceis tanto para clássicos quanto para quânticos. Famílias candidatas:
| Família | Problema difícil | Maturidade |
|---|---|---|
| Reticulados (lattices) | achar o vetor mais curto / LWE | ✅ a base dos padrões |
| Hash-based | só resistência de hash | ✅ assinaturas, ultraconservador |
| Código-corretor | decodificar código aleatório | ✅ KEM (McEliece) |
| Isogenias | caminhos entre curvas | ❌ SIKE quebrado em 2022 |
| Multivariada | sistemas polinomiais | ⚠️ vários quebrados |
2.2 Reticulados, em intuição
Um reticulado é uma grade infinita de pontos no espaço de muitas dimensões. Dois problemas nele são difíceis mesmo para o quântico:
- SVP — achar o ponto não-nulo mais próximo da origem.
- LWE (Learning With Errors) — resolver um sistema linear ao qual se
somou um ruído pequeno. Sem o ruído é álgebra trivial; com ele, vira inviável em alta dimensão.
A graça: a matemática é rápida (vetores e matrizes pequenas), o que torna os esquemas de reticulado competitivos em velocidade — o preço são chaves e assinaturas maiores que as das curvas elípticas.
2.3 Os padrões NIST (2024)
A NIST finalizou os primeiros padrões em agosto de 2024. Os nomes mudaram (de nome de competição para nome FIPS):
| Padrão | Era | Tipo | Base | Uso |
|---|---|---|---|---|
| ML-KEM (FIPS 203) | Kyber | KEM (troca de chave) | reticulado | o default para sigilo |
| ML-DSA (FIPS 204) | Dilithium | assinatura | reticulado | o default para assinar |
| SLH-DSA (FIPS 205) | SPHINCS+ | assinatura | só hash | hedge conservador, lento |
| FN-DSA (FALCON) | Falcon | assinatura | reticulado | assinaturas compactas |
- ML-KEM substitui ECDH: encapsula uma chave de sessão. É o foco número um da
migração (por causa do HNDL).
- ML-DSA substitui Ed25519/RSA para assinaturas; SLH-DSA existe para quem
quer confiar só na segurança de hash (sem apostar em reticulados), aceitando assinaturas grandes e lentas.
2.4 A lição do SIKE: humildade
Nem todo candidato sobreviveu. O SIKE (baseado em isogenias) era uma das promessas mais elegantes — chaves minúsculas — e foi quebrado em 2022 por um PC comum, em uma tarde, com matemática clássica. Já estava na reta final do processo NIST.
A moral reforça o princípio de Kerckhoffs: só a criptanálise pública e prolongada dá confiança. É por isso que a migração recomendada é híbrida — combinar o novo com o clássico, para que uma quebra futura de qualquer um dos lados não derrube tudo (próxima seção).
Referência densa: parâmetros, tamanhos e performance de ML-KEMML-DSA SLH-DSA/FALCON, McEliece e HQC em
08-pos-quantica. A seguir: A migração — o que fazer, em que ordem, e por quê o modo híbrido.