Capítulo 23 — Segurança quântica e pós-quântica: métodos I | Graduação Segurança quântica e pós-quântica

Ensino gratuito e aberto para quem deseja proteger pessoas e tecnologias. Não é preciso criar uma conta para estudar ou consultar as respostas.

Mapa da aula

Aula 23 publicada. Mapa, exemplo, EX045.

flowchart TD
  N0["23.1 Learning With Errors"]
  N1["23.2 Atividade prática — Laboratório W"]
  N2["23.3 Do LWE ao ML-KEM"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3
  N3 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX045"]

Desenho lógico

flowchart LR
  N0["23.1 Learning With Errors"]
  N1["23.2 Atividade prática — Laboratório W"]
  N2["23.3 Do LWE ao ML-KEM"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3 --> Q["EX045"]

[23.1 Learning With Errors]
    |
    v
[23.2 Atividade prática — Laboratório W]
    |
    v
[23.3 Do LWE ao ML-KEM]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX045]

Objetivos de aprendizagem

Você vai (1) enunciar o problema Learning With Errors (LWE); (2) executar uma cifração LWE de brinquedo e explicar por que a decifração funciona; (3) descrever como o ML-KEM transforma essa ideia num KEM; e (4) explicar os conjuntos de parâmetros e as categorias de segurança.

23.1 Learning With Errors

Dada uma matriz aleatória A módulo q e um vetor b = As + e, em que s é secreto e e é um vetor de pequenos erros aleatórios, recupere s. Sem e, a eliminação gaussiana resolve o sistema rapidamente. Com e, os melhores algoritmos clássicos e quânticos conhecidos levam tempo exponencial na dimensão, porque o problema passa a ser encontrar vetores curtos em reticulados de alta dimensão. Regev (2009) introduziu o LWE e mostrou que a sua dificuldade se relaciona com problemas de reticulados no pior caso. O ML-KEM usa uma variante estruturada, o Module-LWE, sobre os anéis de polinômios do Capítulo 6.

23.2 Atividade prática — Laboratório W

# Lab W (ch 23): a TOY Regev-style LWE encryption of one bit. Deliberately insecure parameters.
import random
rng = random.Random(5)
n, q, m = 16, 3329, 64
def small(): return rng.choice([-2, -1, 0, 1, 2])
s = [rng.randrange(q) for _ in range(n)]
A = [[rng.randrange(q) for _ in range(n)] for _ in range(m)]
b = [(sum(A[i][j] * s[j] for j in range(n)) + small()) % q for i in range(m)]   # b = A s + e
def enc(bit):
    r = [rng.randrange(2) for _ in range(m)]                                        # random subset
    u = [sum(r[i] * A[i][j] for i in range(m)) % q for j in range(n)]
    v = (sum(r[i] * b[i] for i in range(m)) + bit * (q // 2)) % q
    return u, v
def dec(u, v):
    d = (v - sum(u[j] * s[j] for j in range(n))) % q                                 # = bit*q/2 + small noise
    return 1 if q // 4 < d < 3 * q // 4 else 0
ok = sum(dec(*enc(bit)) == bit for bit in [rng.randrange(2) for _ in range(2000)])
print(f"toy LWE: {ok}/2000 bits decrypted correctly (noise stays below q/4)")

Saída esperada:

toy LWE: 2000/2000 bits decrypted correctly (noise stays below q/4)

Para cifrar um bit, somam-se um subconjunto aleatório das linhas; o ruído acumulado continua pequeno, enquanto o bit é posto em q/2. Quem decifra remove a parte que depende de s e verifica se o resto está mais perto de 0 ou de q/2. Os parâmetros aqui são de brinquedo — um segredo de 16 dimensões é fácil de recuperar — e servem apenas para mostrar o mecanismo.

Rodar o laboratório várias vezes com escolhas aleatórias diferentes mostra que a decifração continua dando certo, porque o ruído fica abaixo do limiar.

23.3 Do LWE ao ML-KEM

O ML-KEM (FIPS 203) usa o Module-LWE com polinômios de 256 coeficientes, comprime os textos cifrados e envolve a cifração numa transformação (uma variante da Fujisaki–Okamoto), de modo que o desencapsulamento recifra e confere o texto cifrado, o que protege contra ataques de texto cifrado escolhido. A interface é um KEM: o KeyGen produz uma chave de encapsulamento e uma chave de desencapsulamento; o Encaps produz um texto cifrado e um segredo compartilhado de 32 bytes; o Decaps recupera o segredo. Os conjuntos de parâmetros ML-KEM-512, -768 e -1024 visam as categorias 1, 3 e 5 do NIST. As chaves de encapsulamento têm 800, 1.184 e 1.568 bytes; os textos cifrados, 768, 1.088 e 1.568 bytes.

23.4 Exemplo resolvido

A HCU escolhe o ML-KEM-768 para a troca de chaves híbrida porque a categoria 3 oferece uma margem acima da segurança equivalente ao AES-128, é o conjunto de parâmetros usado pelo grupo TLS X25519MLKEM768, amplamente implantado, e a sua chave de 1.184 bytes cabe nos handshakes típicos. O ML-KEM-1024 fica reservado para qualquer parceiro cujas regras exijam a categoria 5.

A escolha é registrada com os seus motivos para que possa ser revista se as orientações mudarem. As chaves e os textos cifrados maiores foram medidos no laboratório antes de a escolha ser confirmada, e os enlaces das agências os comportaram sem mudanças na rede.

23.5 Erros comuns e limites

Achar que os parâmetros do laboratório de brinquedo são seguros.
Esquecer que o ML-KEM é um KEM, e não uma função de cifração genérica.
Escolher os parâmetros apenas pelo tamanho, sem considerar os requisitos de política.

Os parâmetros de brinquedo são escolhidos para que quem lê consiga acompanhar a aritmética, o que significa que um atacante também conseguiria. Um KEM produz um segredo compartilhado que uma cifra simétrica depois usa; ele não cifra mensagens arbitrárias diretamente. A escolha dos parâmetros depende da categoria de segurança, da política e do suporte nos protocolos, além do tamanho. Um conjunto menor pode servir para a maioria dos usos, mas as regras de um parceiro podem exigir um maior, qualquer que seja o desempenho.

Exercícios

EX045 — Por que o ruído importa. Explique em três frases por que o LWE sem erro é fácil e com erro é considerado difícil. Rubrica: 3 = argumento da álgebra linear versus o dos vetores curtos em reticulados.
EX046 — Escolha de parâmetros. O parceiro da HCU exige a categoria 5 para o estabelecimento de chaves. Qual conjunto ML-KEM, e quantos bytes têm a chave de encapsulamento e o texto cifrado? Rubrica: 3 = ML-KEM-1024, 1.568 e 1.568 bytes.

Síntese

O LWE esconde um segredo sob um pequeno ruído; o ML-KEM constrói sobre a sua variante modular um KEM eficiente e seguro contra texto cifrado escolhido, com três conjuntos de parâmetros associados às categorias do NIST.