CRYSTALS-Kyber.

CRYSTALS-Kyber é um mecanismo de encapsulação de chave (KEM) cuja segurança se reduz ao problema Module Learning With Errors (MLWE) sobre reticulados estruturados. O NIST selecionou-o em 2022 como KEM principal do processo PQC e finalizou-o em agosto de 2024 como FIPS 203 (ML-KEM). A norma define três conjuntos de parâmetros — ML-KEM-512, ML-KEM-768 e ML-KEM-1024 — visando as categorias de segurança NIST 1, 3 e 5, com chaves públicas de aproximadamente 800, 1184 e 1568 bytes e cifras de tamanho comparável.

Internamente, um esquema de chave pública IND-CPA é reforçado num KEM IND-CCA2 através de uma transformação Fujisaki–Okamoto: a desencapsulação volta a cifrar a mensagem recuperada e rejeita qualquer divergência, de forma que uma cifra adulterada produz uma chave pseudoaleatória de "rejeição implícita" em vez de revelar segredos. Como um adversário do tipo store-now-decrypt-later poderia arquivar o tráfego de hoje para um futuro computador quântico, o Kyber é implementado em modo híbrido (por exemplo X25519MLKEM768), onde um atacante teria de quebrar simultaneamente a metade clássica e a metade pós-quântica.

A segurança da implementação importa tanto como a matemática. A divulgação KyberSlash (2024) mostrou que uma divisão inteira dependente do segredo pelo módulo q = 3329 era de tempo variável em muitos CPUs; medir o tempo da desencapsulação de cifras forjadas podia recuperar bits da chave. O KyberSlash1 e o KyberSlash2 foram corrigidos no código de referência (dezembro de 2023) substituindo divisões por multiplicações, e as correções propagaram-se para liboqs, PQClean, CIRCL, AWS-LC e Botan.

flowchart LR
  KG[Geracao de chaves] --> PK[Chave publica pk]
  KG --> SK[Chave secreta sk]
  PK --> ENC[Encapsular: escolher m, derivar K e cifra c]
  ENC --> C[Cifra c]
  ENC --> KS1[Segredo partilhado K]
  C --> DEC[Desencapsular com sk mais verificacao de recifragem FO]
  SK --> DEC
  DEC -->|coincide| KS2[Mesmo segredo partilhado K]
  DEC -->|diverge| REJ[Rejeicao implicita: chave pseudoaleatoria]