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

Algoritmos resistentes a computadores quânticos. *hor (1994)*quebra IFP, DLP, ECDLP — destrói RSA, DH, ECC. *rover (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, hashbased, codebased, 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.

*ap pra cryptanalysisrelevant* precisa *ogical qubits*(não físicos). Estimativas: 20M qubits físicos para fatorar RSA2048 (Gidney + Ekerå 2019). Possivelmente 2030–2040; talvez nunca; *ão dá pra apostar*

Grover (1996)

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

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

*ecomendação* AES256 e SHA384/SHA3384 mínimo para cenário pósquântico. SHA256 considerado limítrofe.

"Harvest Now, Decrypt Later" (HNDL)

Atacantes podem coletar tráfego cifrado *oje*(TLS, VPN, encrypted backups) e armazenar até quantum estar disponível. *udo 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 *gora*

2. Problema NIST PQC Process

Padrões NIST finalizados (ago/2024)

Acrônimos novos

NIST renomeou:

• *RYSTALSKyber*→ *LKEM*(ModuleLatticebased KEM).
• *RYSTALSDilithium*→ *LDSA*(ModuleLatticebased DSA).
• *PHINCS+*→ *LHDSA*(Stateless Hashbased DSA).
• *ALCON*→ *NDSA*(FastFourieroverNTRU 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

• *VP (Shortest Vector Problem)* achar vetor não-zero mais curto.
• *VP (Closest Vector Problem)* dado ponto, achar lattice point mais próximo.
• *WE (Learning With Errors)*— Regev 2005: dado \((A, A\mathbf{s} + \mathbf{e})\) onde \(\mathbf{e}\) é small noise, achar \(\mathbf{s}\).
• *odule-LWE*— variante estruturada usada em Kyber/Dilithium.
• *ing-LWE*— extra structure.
• *TRU*— HoffsteinPipherSilverman 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: *os, Ducas, Kiltz, Lepoint, Lyubashevsky, Schanck, Schwabe, Seiler, Stehlé* 2017–2022.

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

Variantes

Performance (3GHz CPU)

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

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

Adoção

• *LS 1.3*hybrid X25519MLKEM768 — Cloudflare (set2024), Google Chrome (mai2024), Firefox (out/2024).
• *penSSH*— sntrup761x25519 ainda dominante; ML-KEM coming.
• *pple iMessage PQ3*— Curve25519 + Kyber-1024.
• *ignal PQXDH*— X25519 + MLKEM1024 (set/2023).
• *WS KMS, Google Cloud KMS*— pilots em 2024.

Hybrid mode

Combine KEM clássica + PQC. Atacante precisa quebrar *mbos*

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: *ai, Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, Stehlé*

Latticebased signature (FiatShamir + Aborts paradigm).

Variantes

Performance

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

*rade-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

*ash-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.

*tateless*(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).
• *ão usa lattice*— segurança baseada *penas*em propriedades de hash. Conservadoramente seguro mesmo se lattice for quebrada.
• *entidão*é o trade-off.

Variantes (FIPS 205)

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

Performance (-128f)

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

*ign é 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)

• *MSS*(RFC 8391) — stateful, eficiente, mas *RÍTICO* state reuse = chave comprometida.
• *MS*(RFC 8554) — similar.
• *SS*— multi-tree LMS.
• NIST SP 800-208 (2020) — usa para firmware signatures restritas.

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

*astFourierbased NTRU signatures* Fouque, Hoffstein, Kirchner, Lyubashevsky, Pornin, Prest, Ricosset, Seiler, Whyte, Zhang.

*atticebased, NTRUbased* Mais difícil de implementar (floatingpoint arithmetic), mas signatures *uito menores*que MLDSA.

Variantes

Performance

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

Tradeoff vs MLDSA

• FNDSA: menor signature, mais difícil impl (FP), constanttime challenging.
• MLDSA: maior signature, simpler impl, integeronly.

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

8. HQC — RFC selected mar/2025

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

*odebased KEM*— segurança baseada em decoding random linear codes (problema clássico, McEliecestyle).

NIST escolheu HQC como *ackup*de MLKEM em caso de quebra de lattice. Principalmente porque codebased foi estudado por *0 anos*(McEliece 1978).

Variantes

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

9. Code-based: Classic McEliece

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

*roblema* chave pública gigantesca.

Inviável para web TLS handshake. Usado apenas em situações específicas (storage onetime 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 *Q problem*(Multivariate Quadratic): resolver sistema polinomial não-linear sobre \(\mathbb{F}_q\).

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

• *ainbow*— finalista Round 3 — quebrado por *eullens*(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)

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

*IKE*alternative em NIST Round 4 (2022).

*uebrado em jul/2022*por *outer Castryck + Thomas Decru*(KU Leuven). Algoritmo polinomial em laptop em ~1 hora. Usa *lueandsplit*atacando a torção. Choque na comunidade — área foi para ferro morto.

CSIDH

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

*ição* PQC é nova, baseada em problemas pouco estudados; *edundâ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.

*imeline NSA*

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

Aproach genérica

1. *nventariar*uso de RSA, DH, ECC.
2. *riorizar*por valor de longo prazo dos dados (HNDL risk).
3. *ybrid first*— adicionar PQC sem remover clássica (atacante precisa ambas).
4. *est em pilot*— TLS termination edge primeiro.
5. *igrar PKI*— root CAs com SLHDSA ou MLDSA; intermediates podem ser hybrid.
6. *otate firmware signing keys*para LMS/XMSS para boot validation.
7. *onitor*quebra de algoritmos PQC; preparar migração re-revisitada.

Implementações disponíveis

• *iboqs*(Open Quantum Safe) — biblioteca C com todas finalistas.
• *penSSL 3.5+*— MLKEM, MLDSA via provider.
• *oringSSL*— Kyber em produção Cloudflare/Google.
• *ouncycastle (Java)*— full PQC suite.
• *olfSSL*— embedded targeted PQC.
• *LKEMReference*(NIST), *iboqsgo* *iboqsrust*bindings.
• *yber-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.
• *FC 8391*XMSS, *FC 8554*LMS — já padronizados.

13. PQC além de NIST

China

CSTC (Chinese Standardization Technical Committee) 260 publicou seu próprio processo PQC. *igisSig* *AC* *M9*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 *IDAS 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ósSIKE), Mayo (multivariate), HAWK (lattice), MIRATH (rank metric), SDitH (zeroknowledge), MAYO, etc.
• Round 2 (2024–) — narrowing.

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

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

15. Fully Homomorphic Encryption (FHE)

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

Esquemas

• *FV*(BrakerskiFanVercauteren) — integer arithmetic.
• *GV*(BrakerskiGentryVaikuntanathan) — leveled.
• *KKS*(CheonKimKimSong) — approximate (floatingpoint).
• *FHE*(ChillottiGamaGeorgieva-Izabachène) — boolean gates, fast bootstrap.
• *HEW*— boolean.

Performance

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

Bibliotecas

• *penFHE*(DARPA) — BGVBFVCKKSTFHEFHEW.
• *icrosoft SEAL*— BFV/CKKS.
• *oncrete / TFHE-rs*(Zama) — TFHE.
• *Elib*(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. *ão FHE*— usa secret sharing + interactive protocols.

Frameworks

• *P-SPDZ*(Bristol).
• *MPtoolkit*(Wang et al.) — semihonest e malicious.
• *OTION*(TU Darmstadt).
• *BY3*— three-party para ML.

Aplicações

• *hreshold signatures*(Bitcoin custodial).
• *rivate auctions*
• *ederated learning*com aggregation segura.
• *enomic data analysis*
• *oston Women's Workforce Council*salary parity study (2017) — first prod MPC use case publicizado.

17. Zero-Knowledge Proofs (ZKP)

GoldwasserMicaliRackoff 1985. Prove statement sem revelar testemunha.

Categorias

• *nteractive* Σ-protocols, Schnorr.
• *oninteractive (NIZK)* FiatShamir transform.
• *kSNARKs* Succinct, Noninteractive, Argument of Knowledge. Pequenos (~200 bytes), constante-time verify. Trusted setup (com ceremony).
• *k-STARKs* Scalable, Transparent (no trusted setup), maior (~50 KB).
• *ulletproofs* range proofs sem trusted setup, \(O(\log n)\).
• *LONK, 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:

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

• *ernstein, Buchmann, Dahmen*(eds.), Post-Quantum Cryptography, Springer 2009.
• *IST PQC pages* csrc.nist.gov/Projects/post-quantum-cryptography.
• *pen Quantum Safe* openquantumsafe.org.
• *loudflare PQC blog* blog.cloudflare.com/pq-2024/.
• *QCrystals website* `pqcrystals.org`.
• *PHINCS+ website* sphincs.org.
• *eal 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.