08 — Criptografia Pós-Quântica (PQC)

Algoritmos resistentes a computadores quânticos. Shor (1994) quebra IFP, DLP, ECDLP — destrói RSA, DH, ECC. Grover (1996) dá speedup quadrático em busca — implica chaves simétricas/hash precisam dobrar.

PQC usa problemas que (presumivelmente) são duros mesmo com quantum: lattices, hash-based, code-based, multivariate, isogenies (uma quebrada).

1. Ameaça quântica

Shor (1994)

Em quantum computer com \(\sim 4000\) qubits estáveis e gates suficientes, fatora \(N\) de 2048 bits em horas. Estado atual (2026):

  • IBM Condor (2023) — 1121 qubits físicos noisy.
  • IBM Heron (2024) — 156 qubits com error correction parcial.
  • Google Willow (2024) — 105 qubits, primeira demo de error correction abaixo de threshold.
  • Quantinuum H2 — 56 qubits trapped-ion, alta fidelidade.

Gap pra cryptanalysis-relevant: precisa logical qubits (não físicos). Estimativas: 20M qubits físicos para fatorar RSA-2048 (Gidney + Ekerå 2019). Possivelmente 2030–2040; talvez nunca; não dá pra apostar.

Grover (1996)

Search em base de tamanho \(N\) em \(O(\sqrt{N})\) queries. Implica:

  • AES-128 → 64-bit segurança quântica → insuficiente.
  • AES-256 → 128-bit segurança quântica → OK.
  • SHA-256 collision → ~\(2^{85}\) (BHT) → ainda OK; some debate.
  • SHA-256 preimage → \(2^{128}\) Grover → OK.

Recomendação: AES-256 e SHA-384/SHA-3-384 mínimo para cenário pós-quântico. SHA-256 considerado limítrofe.

"Harvest Now, Decrypt Later" (HNDL)

Atacantes podem coletar tráfego cifrado hoje (TLS, VPN, encrypted backups) e armazenar até quantum estar disponível. Tudo cifrado com RSAECDHECC hoje está sob ameaça retrospectiva.

Por isso a urgência: dados sensitivos com valor de longo prazo (segredos de Estado, IP, dados médicos) precisam de PQC agora.

2. Problema NIST PQC Process

Round Ano Submissões
Round 1 2017 69
Round 2 2019 26
Round 3 2020 7 finalists + 8 alternates
Selection jul/2022 4 algoritmos para padronização
Round 4 2022–2024 KEM backups (BIKE, HQC, Classic McEliece, SIKE)
HQC selected mar/2025 KEM backup confirmado
Round Signatures 2023–em curso competição extra para signatures

Padrões NIST finalizados (ago/2024)

Padrão Algoritmo Tipo Variant Round 3
FIPS 203 ML-KEM KEM CRYSTALS-Kyber
FIPS 204 ML-DSA Signature CRYSTALS-Dilithium
FIPS 205 SLH-DSA Signature SPHINCS+
FIPS 206 (draft) FN-DSA Signature FALCON

Acrônimos novos

NIST renomeou:

  • CRYSTALS-Kyber → ML-KEM (Module-Lattice-based KEM).
  • CRYSTALS-Dilithium → ML-DSA (Module-Lattice-based DSA).
  • SPHINCS+ → SLH-DSA (Stateless Hash-based DSA).
  • FALCON → FN-DSA (Fast-Fourier-over-NTRU DSA).

3. Lattice-based — base matemática

Lattice

\(\Lambda = \{ \sum b_i \mathbf{v}_i : b_i \in \mathbb{Z} \}\) — combinação inteira de vetores base \(\mathbf{v}_i\).

Problemas duros

  • SVP (Shortest Vector Problem): achar vetor não-zero mais curto.
  • CVP (Closest Vector Problem): dado ponto, achar lattice point mais próximo.
  • LWE (Learning With Errors) — Regev 2005: dado \((A, A\mathbf{s} + \mathbf{e})\) onde \(\mathbf{e}\) é small noise, achar \(\mathbf{s}\).
  • Module-LWE — variante estruturada usada em Kyber/Dilithium.
  • Ring-LWE — extra structure.
  • NTRU — Hoffstein-Pipher-Silverman 1996, polynomial ring problem.

Por que duros?

LWE reduz a worst-case lattice problems (SIVP, GapSVP) — Regev's reduction. Significa: solver médio LWE → solver pior caso lattice. Não há quantum algorithm conhecido para SVP além de speedup polinomial pequeno.

4. ML-KEM (Kyber) — FIPS 203

CRYSTALS-Kyber: Bos, Ducas, Kiltz, Lepoint, Lyubashevsky, Schanck, Schwabe, Seiler, Stehlé. 2017–2022.

KEM (Key Encapsulation Mechanism) — não cifra mensagem; gera shared secret + ciphertext que recipient decapsula com private key.

Variantes

Variant Security Public Key Ciphertext Shared Secret
ML-KEM-512 NIST L1 (~AES-128) 800 B 768 B 32 B
ML-KEM-768 NIST L3 (~AES-192) 1184 B 1088 B 32 B
ML-KEM-1024 NIST L5 (~AES-256) 1568 B 1568 B 32 B

Performance (3GHz CPU)

  • Keygen: ~50 µs
  • Encap: ~70 µs
  • Decap: ~80 µs

Mais rápido que ECDH em CPU sem ECC accel. Tamanhos maiores que ECC (32 B → 1.5 KB).

Adoção

  • TLS 1.3 hybrid X25519MLKEM768 — Cloudflare (set2024), Google Chrome (mai2024), Firefox (out/2024).
  • OpenSSH — sntrup761x25519 ainda dominante; ML-KEM coming.
  • Apple iMessage PQ3 — Curve25519 + Kyber-1024.
  • Signal PQXDH — X25519 + ML-KEM-1024 (set/2023).
  • AWS KMS, Google Cloud KMS — pilots em 2024.

Hybrid mode

Combine KEM clássica + PQC. Atacante precisa quebrar ambos:

shared = KDF(X25519_shared \\\| ML_KEM_shared \\\| context)

Padrão durante migração; abandona-se hybrid quando confiança em PQC consolidada.

5. ML-DSA (Dilithium) — FIPS 204

CRYSTALS-Dilithium: Bai, Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, Stehlé.

Lattice-based signature (Fiat-Shamir + Aborts paradigm).

Variantes

Variant Security Public Key Signature
ML-DSA-44 NIST L2 1312 B 2420 B
ML-DSA-65 NIST L3 1952 B 3293 B
ML-DSA-87 NIST L5 2592 B 4595 B

Performance

  • Keygen: ~70 µs
  • Sign: ~250 µs (variável devido a rejection sampling)
  • Verify: ~80 µs

Trade-off: assinatura ~3 KB vs Ed25519 64 B. Pubkey ~2 KB vs Ed25519 32 B. Custo significativo para certificados X.509 (impacta tamanho de cert chain TLS).

Adoção

  • Apple iMessage PQ3 contém Dilithium além de Kyber para signing.
  • IETF draft tls-mldsa-signature em curso.
  • X.509 — id-ml-dsa-44/65/87 em RFC 9810/draft.
  • WebAuthn passkeys: PQC roadmap em curso.

6. SLH-DSA (SPHINCS+) — FIPS 205

Hash-based signatures. Bernstein, Hülsing, Andreeva, Andersen, Aumasson, Buchmann, Castelnovi, Cid, Fluhrer, Gazdag, Hülsing, Kampanakis, Kölbl, Lange, Lauridsen, Mendel, Niederhagen, Reijnders, Rijneveld, Schwabe.

Stateless (não precisa rastrear contador de assinaturas, ao contrário de XMSS, LMS).

Como funciona

  • Construído sobre Merkle trees + WOTS+ (Winternitz One-Time Signature) + FORS (Forest of Random Subsets).
  • Não usa lattice — segurança baseada apenas em propriedades de hash. Conservadoramente seguro mesmo se lattice for quebrada.
  • Lentidão é o trade-off.

Variantes (FIPS 205)

Param set Hash Sig size
SLH-DSA-SHA2-128s SHA-256 7856 B
SLH-DSA-SHA2-128f SHA-256 17088 B
SLH-DSA-SHA2-192s SHA-384 16224 B
SLH-DSA-SHA2-192f SHA-384 35664 B
SLH-DSA-SHA2-256s SHA-512 29792 B
SLH-DSA-SHA2-256f SHA-512 49856 B
SLH-DSA-SHAKE-128s/f SHAKE similar

s = small (signature menor, slower), f = fast (signature maior, faster).

Performance (-128f)

  • Keygen: ~5 ms
  • Sign: ~150 ms (!!!)
  • Verify: ~5 ms

Sign é 1000× mais lento que Ed25519. Por isso uso restrito a:

  • Code signing (raro, alto valor).
  • Firmware updates.
  • Root certificates (assinam pouco).
  • Long-term archival signatures.

Hash-based (variantes statefuls)

  • XMSS (RFC 8391) — stateful, eficiente, mas CRÍTICO: state reuse = chave comprometida.
  • LMS (RFC 8554) — similar.
  • HSS — multi-tree LMS.
  • NIST SP 800-208 (2020) — usa para firmware signatures restritas.

7. FN-DSA (FALCON) — FIPS 206 draft

Fast-Fourier-based NTRU signatures. Fouque, Hoffstein, Kirchner, Lyubashevsky, Pornin, Prest, Ricosset, Seiler, Whyte, Zhang.

Lattice-based, NTRU-based. Mais difícil de implementar (floating-point arithmetic), mas signatures muito menores que ML-DSA.

Variantes

Variant Security Public Key Signature
FN-DSA-512 NIST L1 897 B ~666 B
FN-DSA-1024 NIST L5 1793 B ~1280 B

Performance

  • Sign: ~3 ms (slower que ML-DSA)
  • Verify: ~50 µs (faster que ML-DSA)

Trade-off vs ML-DSA

  • FN-DSA: menor signature, mais difícil impl (FP), constant-time challenging.
  • ML-DSA: maior signature, simpler impl, integer-only.

ML-DSA é o "default" pra quase tudo; FN-DSA quando tamanho é crítico (e.g., bandwidth-constrained channels).

8. HQC — RFC selected mar/2025

Hamming Quasi-Cyclic — Aguilar Melchor, Aragon, Bettaieb, Bidoux, Blazy, Deneuville, Gaborit, Persichetti, Zémor.

Code-based KEM — segurança baseada em decoding random linear codes (problema clássico, McEliece-style).

NIST escolheu HQC como backup de ML-KEM em caso de quebra de lattice. Principalmente porque code-based foi estudado por 50 anos (McEliece 1978).

Variantes

Variant Security Public Key Ciphertext
HQC-128 NIST L1 2249 B 4481 B
HQC-192 NIST L3 4522 B 9026 B
HQC-256 NIST L5 7245 B 14469 B

Maior que Kyber. Adoção será nicho.

9. Code-based: Classic McEliece

McEliece 1978 — mais antigo PQC. Goppa codes. Robusto, confiança histórica enorme.

Problema: chave pública gigantesca.

Variant Public Key
mceliece348864 261 KB
mceliece6960119 1 MB
mceliece8192128 1.4 MB

Inviável para web TLS handshake. Usado apenas em situações específicas (storage one-time keys, B2B com chaves pré-distribuídas).

NIST não padronizou (Round 4); algoritmo está disponível na liboqs.

10. Multivariate (perdedores notáveis)

Baseados em MQ problem (Multivariate Quadratic): resolver sistema polinomial não-linear sobre \(\mathbb{F}_q\).

HFEv-, Rainbow, GeMSS — todos quebrados ou enfraquecidos durante NIST process.

  • Rainbow — finalista Round 3 — quebrado por Beullens (2022) em laptop em ~50 horas. Eliminado dramatically tarde.

Multivariate ainda área de pesquisa; nenhum padrão NIST.

11. Isogeny-based — drama

SIDH / SIKE (perdedor catastrófico)

Supersingular Isogeny Diffie-Hellman. Jao + de Feo 2011. Atrativo: chaves muito pequenas (~330 B).

SIKE alternative em NIST Round 4 (2022).

Quebrado em jul/2022 por Wouter Castryck + Thomas Decru (KU Leuven). Algoritmo polinomial em laptop em ~1 hora. Usa glue-and-split atacando a torção. Choque na comunidade — área foi para ferro morto.

CSIDH

Variante diferente — não foi quebrada. Mas adoção mínima.

Lição: PQC é nova, baseada em problemas pouco estudados; redundância (lattice + hash + code) crítica.

12. Migração prática

CNSA 2.0 (NSA, 2022)

NSA Cybersecurity Advisory: requer transição PQC para sistemas classified.

Categoria Algorithm Uso
Asymmetric KEM ML-KEM-1024 Replace ECDH/RSA
Signature ML-DSA-87 Replace ECDSA/RSA
Long-term assinatura LMS / XMSS Stateful firmware
Symmetric AES-256 Continua
Hash SHA-384 ou SHA-512 Continua

Timeline NSA:

  • 2025: novos sistemas devem suportar PQC.
  • 2030: software conforming exigido.
  • 2033: hardware conforming exigido.

Aproach genérica

  1. Inventariar uso de RSA, DH, ECC.
  2. Priorizar por valor de longo prazo dos dados (HNDL risk).
  3. Hybrid first — adicionar PQC sem remover clássica (atacante precisa ambas).
  4. Test em pilot — TLS termination edge primeiro.
  5. Migrar PKI — root CAs com SLH-DSA ou ML-DSA; intermediates podem ser hybrid.
  6. Rotate firmware signing keys para LMS/XMSS para boot validation.
  7. Monitor quebra de algoritmos PQC; preparar migração re-revisitada.

Implementações disponíveis

  • liboqs (Open Quantum Safe) — biblioteca C com todas finalistas.
  • OpenSSL 3.5+ — ML-KEM, ML-DSA via provider.
  • BoringSSL — Kyber em produção Cloudflare/Google.
  • bouncycastle (Java) — full PQC suite.
  • wolfSSL — embedded targeted PQC.
  • ML-KEM-Reference (NIST), liboqs-go, liboqs-rust bindings.
  • kyber-py — pure Python reference.

Padrões IETF

  • draft-ietf-pquip-* — PQC use guidance.
  • draft-ietf-tls-hybrid-design — hybrid TLS 1.3.
  • draft-ietf-tls-mldsa — TLS auth com ML-DSA.
  • draft-ietf-cose-dilithium — JOSE/COSE com Dilithium.
  • RFC 8391 XMSS, RFC 8554 LMS — já padronizados.

13. PQC além de NIST

China

CSTC (Chinese Standardization Technical Committee) 260 publicou seu próprio processo PQC. Aigis-Sig, LAC, SM9-PQ. Não NIST-aligned.

Coreia

KpqC (Korea PQ Crypto): NTRU+, SMAUG, REDOG. Pilot in 2024–2026.

Europa

ENISA segue NIST mas tem perfil mais cauteloso. Adoção via eIDAS 2.0.

NIST extra signatures (2023–em curso)

Competição adicional para diversificar signatures:

  • 50 submissões iniciais.
  • Round 1 incluiu: SQIsign (isogeny — único pós-SIKE), Mayo (multivariate), HAWK (lattice), MIRATH (rank metric), SDitH (zero-knowledge), MAYO, etc.
  • Round 2 (2024–) — narrowing.

14. Performance comparativa real (cycles, M2/Ryzen)

Operação RSA-3072 Ed25519 ML-KEM-768 ML-DSA-65 SLH-DSA-128f X25519+MLKEM768 (hybrid)
Keygen ~30 ms 50 µs 45 µs 70 µs 5 ms 100 µs
Encap/Sign 3 ms 25 µs 70 µs 250 µs 150 ms 120 µs
Decap/Verify 100 µs 50 µs 80 µs 80 µs 5 ms 130 µs
Pubkey size 384 B 32 B 1184 B 1952 B 32 B 1216 B
Sig/CT size 384 B 64 B 1088 B 3293 B 17088 B 1120 B

PQC adiciona ~1 KB extra ao TLS handshake mas é mais rápido que RSA. Pra signatures o overhead é maior em tamanho.

15. Fully Homomorphic Encryption (FHE)

PQC não-NIST mas relacionado. Crypto que computa sobre dados cifrados sem decifrar.

Esquemas

  • BFV (Brakerski-Fan-Vercauteren) — integer arithmetic.
  • BGV (Brakerski-Gentry-Vaikuntanathan) — leveled.
  • CKKS (Cheon-Kim-Kim-Song) — approximate (floating-point).
  • TFHE (Chillotti-Gama-Georgieva-Izabachène) — boolean gates, fast bootstrap.
  • FHEW — boolean.

Performance

  • ~10⁵–10⁶ vezes mais lento que computação plaintext.
  • Bootstrap (refresh noise) é caro: ~50 ms por gate em TFHE moderno.

Bibliotecas

  • OpenFHE (DARPA) — BGVBFVCKKSTFHEFHEW.
  • Microsoft SEAL — BFV/CKKS.
  • Concrete / TFHE-rs (Zama) — TFHE.
  • HElib (IBM) — BGV.

Aplicações reais

  • ML inference em encrypted data (Microsoft Edge ML pilots).
  • Private set intersection.
  • Encrypted database queries (limitada).

16. MPC — Multi-Party Computation

Compute função sobre inputs privados sem revelar. Não FHE — usa secret sharing + interactive protocols.

Frameworks

  • MP-SPDZ (Bristol).
  • EMP-toolkit (Wang et al.) — semi-honest e malicious.
  • MOTION (TU Darmstadt).
  • ABY3 — three-party para ML.

Aplicações

  • Threshold signatures (Bitcoin custodial).
  • Private auctions.
  • Federated learning com aggregation segura.
  • Genomic data analysis.
  • Boston Women's Workforce Council salary parity study (2017) — first prod MPC use case publicizado.

17. Zero-Knowledge Proofs (ZKP)

Goldwasser-Micali-Rackoff 1985. Prove statement sem revelar testemunha.

Categorias

  • Interactive: Σ-protocols, Schnorr.
  • Non-interactive (NIZK): Fiat-Shamir transform.
  • zk-SNARKs: Succinct, Non-interactive, Argument of Knowledge. Pequenos (~200 bytes), constante-time verify. Trusted setup (com ceremony).
  • zk-STARKs: Scalable, Transparent (no trusted setup), maior (~50 KB).
  • Bulletproofs: range proofs sem trusted setup, \(O(\log n)\).
  • PLONK, Halo, Halo2, Nova: SNARKs modernos com universal trusted setup.

Aplicações

  • Zcash (zk-SNARKs Sapling, Halo2).
  • Ethereum L2 rollups (StarkNet, Polygon zkEVM, zkSync, Scroll, Linea).
  • Private credentials (anonymous proof of age/citizenship).
  • Hardware attestation com privacy.

Veja 10-criptomoeda.md para uso em blockchain.

18. Recomendação consolidada (2026)

Para qualquer sistema novo:

Necessidade Use
Encryption simétrica AES-256 ou ChaCha20-Poly1305
Hash SHA-384 ou SHA-3-384 (PQ-conservative)
Key exchange X25519MLKEM768 hybrid
Server signing Ed25519 hoje; planeje ML-DSA-65 migration
Code signing SLH-DSA-128f (long-term) ou Ed25519 + dual sig
Firmware updates LMS ou XMSS (com state management)
Long-term archival sig SLH-DSA
Bandwidth-crítico FN-DSA (FALCON) quando estável
Privacy compute TFHE-rs ou Concrete; OpenFHE
Threshold FROST (Schnorr) ou Lindell-style ECDSA

Anti-patterns 2026

❌ Novos sistemas sem plano PQC (HNDL). ❌ PQC puro sem hybrid em produção (sem track record ainda). ❌ XMSS/LMS sem state management rigoroso (bug = total compromise). ❌ Ignorar tamanho de signature em protocolos com tight bandwidth. ❌ SIKE/SIDH em qualquer lugar (broken).

19. Bibliografia

  • Bernstein, Buchmann, Dahmen (eds.), Post-Quantum Cryptography, Springer 2009.
  • NIST PQC pages: csrc.nist.gov/Projects/post-quantum-cryptography.
  • Open Quantum Safe: openquantumsafe.org.
  • Cloudflare PQC blog: blog.cloudflare.com/pq-2024/.
  • PQ-Crystals website: pq-crystals.org.
  • SPHINCS+ website: sphincs.org.
  • Real World Crypto 2023, 2024, 2025 — sessões PQC.

20. Referência cruzada

  • Algoritmos clássicos sendo substituídos: 05-assimetrica.md (RSA, DH, ECC).
  • TLS hybrid integration: 07-protocolos.md.
  • Quantum hardware projection: ver §1 e Quantum Roadmap external.
  • Confidential Computing como complemento: 09-confidential-computing.md.