Capítulo 24 — Segurança quântica e pós-quântica: métodos I

Mapa da aula

Aula 24 publicada. Mapa, exemplo, EX047.

flowchart TD
  N0["24.2 Cifrar um bit"]
  N1["24.3 Atividade prática — Laboratório W brinquedo, in"]
  N2["24.4 Do brinquedo ao ML-KEM"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3
  N3 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX047"]

Desenho lógico

flowchart LR
  N0["24.2 Cifrar um bit"]
  N1["24.3 Atividade prática — Laboratório W brinquedo, in"]
  N2["24.4 Do brinquedo ao ML-KEM"]
  N3["Síntese"]
  N0 --> N1 --> N2 --> N3 --> Q["EX047"]

[24.2 Cifrar um bit]
    |
    v
[24.3 Atividade prática — Laboratório W brinquedo, in]
    |
    v
[24.4 Do brinquedo ao ML-KEM]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX047]

Objetivos de aprendizagem

Você vai (1) explicar o aprendizado com erros (LWE) e por que o ruído torna difícil a álgebra linear; (2) acompanhar uma cifragem LWE de brinquedo; (3) relacioná-la à estrutura do ML-KEM; e (4) entender o papel da transformação de Fujisaki–Okamoto. O capítulo parte do Capítulo 2 e fundamenta as escolhas de projeto dos Capítulos 25–28.

24.1 Aprendizado com erros

Dada uma matriz aleatória A e b = A·s + e mod q, em que s é secreto e e é um vetor de pequenos erros aleatórios, encontre s. Sem e, isso é eliminação gaussiana. Com e, não se conhece algoritmo eficiente, clássico ou quântico, para parâmetros adequados; Regev (2009) relacionou o LWE a problemas de reticulados no pior caso. Os melhores ataques usam redução de reticulados, cujo custo cresce exponencialmente com a dimensão.

O papel do ruído aparece na dimensão: no Laboratório W, dezesseis incógnitas com erros pequenos são fáceis de resolver por força bruta sobre os erros, enquanto o ML-KEM-768 trabalha com dimensão 768, em que os melhores ataques de redução de reticulados precisam de muito mais trabalho do que qualquer computador consegue fazer.

24.2 Cifrar um bit

Para cifrar um bit, some um subconjunto aleatório de linhas de (A, b): u = ΣrᵢAᵢ, v = Σrᵢbᵢ + bit·⌊q/2⌋. O detentor da chave calcula v − ⟨u, s⟩ = bit·⌊q/2⌋ + ruído pequeno e arredonda. A decifração funciona enquanto o ruído acumulado ficar abaixo de q/4.

No Laboratório W, os erros são no máximo 2 em valor absoluto e o subconjunto tem no máximo 64 linhas, então o ruído acumulado é no máximo 128. Isso está muito abaixo de q/4, que é cerca de 832, então todo bit é decifrado corretamente. Erros maiores ou mais linhas empurrariam o ruído rumo a q/4 e causariam falhas, que é o compromisso que os parâmetros do ML-KEM equilibram com a segurança.

24.3 Atividade prática — Laboratório W (brinquedo, inseguro)

# Lab W (ch 24): 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)

Esses parâmetros são pequenos demais para dar segurança e vazam por muitos caminhos; o laboratório existe só para tornar a álgebra concreta.

O resultado de 2000 em 2000 decorre do limite: um ruído de no máximo 128 nunca pode cruzar o limiar de 832. Mude small() para sortear de −20 a 20 e execute de novo; o ruído no pior caso sobe para 1.280, acima do limiar, mas os 2000 bits continuam sendo decifrados, porque uma soma de cerca de 32 erros aleatórios raramente se aproxima do pior caso; as falhas só aparecem com erros muito maiores, como mostra o exercício EX047. Depois faça-a devolver sempre 0 e resolva s a partir de dezesseis linhas de A e b por eliminação gaussiana, o que mostra que são os erros que carregam a segurança.

24.4 Do brinquedo ao ML-KEM

O ML-KEM substitui os inteiros por polinômios em Z₃₃₂₉[x]/(x²⁵⁶+1) e usa a estrutura de módulo (k = 2, 3 ou 4 vetores de polinômios) para ter chaves compactas, comprime os textos cifrados, sorteia o ruído de uma distribuição binomial centrada e deriva a aleatoriedade com SHAKE. A cifragem de chave pública subjacente só é segura contra atacantes passivos; o ML-KEM aplica uma transformação no estilo Fujisaki–Okamoto — recifrar durante o desencapsulamento e devolver uma chave pseudoaleatória de "rejeição implícita" em caso de divergência — para resistir a ataques de texto cifrado escolhido (FIPS 203).

Cada mudança tem um propósito: polinômios e módulos encolhem as chaves, a compressão economiza bytes e a transformação resiste a ataques ativos.

24.5 Exemplo resolvido

Um engenheiro da BPA pergunta por que o desencapsulamento do ML-KEM recifra. Resposta: para detectar textos cifrados manipulados. Sem essa verificação, um atacante poderia enviar textos cifrados forjados e aprender sobre a chave secreta a partir do sucesso ou não da decifração. As implementações precisam fazer a comparação em tempo constante, ou o tempo da verificação vaza a mesma informação.

A chave de rejeição implícita também importa: devolver um erro em caso de divergência diria, por si só, ao atacante que o texto cifrado era inválido. Ao devolver uma chave pseudoaleatória derivada de um valor secreto, o ML-KEM faz o caso inválido parecer um sucesso normal para o atacante, e o protocolo falha mais adiante de uma forma que nada revela sobre a chave.

24.6 Erros comuns e limites

• Achar que a segurança do LWE vem da matriz, e não do ruído.
• Usar a cifragem segura só contra atacantes passivos sem a transformação FO.
• Tratar o brinquedo como um esquema utilizável.

O Laboratório W mostra o primeiro ponto diretamente: retire os erros e o segredo cai diante da eliminação gaussiana. O esquema seguro só contra passivos, sem a transformação, fica aberto aos ataques de texto cifrado escolhido descritos no exemplo resolvido. O brinquedo usa dimensão dezesseis e nenhuma compressão, então não oferece segurança alguma, e o seu único uso é didático.

Exercícios

• EX047 — Orçamento de ruído. No Laboratório W, mude a escolha dos erros para rng.randint(-150, 150) e depois para rng.randint(-300, 300) e observe a decifração. Explique. Rubrica: 3 = aparecem falhas; explica o ruído acumulado contra q/4.
• EX048 — Propósito da FO. Explique a rejeição implícita a um desenvolvedor em 120 palavras. Rubrica: 3 = raciocínio de texto cifrado escolhido e exigência de tempo constante.

Síntese

O LWE esconde segredos sob ruído; um brinquedo mostra a decifração como arredondamento; o ML-KEM acrescenta estrutura de anel/módulo, compressão e a transformação FO para a segurança contra texto cifrado escolhido.