Capítulo 12 — Probabilidade e estatística | 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 12 publicada. Mapa, exemplo, EX023.

flowchart TD
  N0["12.1 Eventos raros em escala"]
  N1["12.2 Atividade prática — Laboratório P"]
  N2["12.3 Taxas medidas e intervalos"]
  N3["12.4 Taxas de base"]
  N4["Síntese"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX023"]

Desenho lógico

flowchart LR
  N0["12.1 Eventos raros em escala"]
  N1["12.2 Atividade prática — Laboratório P"]
  N2["12.3 Taxas medidas e intervalos"]
  N3["12.4 Taxas de base"]
  N4["Síntese"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX023"]

[12.1 Eventos raros em escala]
    |
    v
[12.2 Atividade prática — Laboratório P]
    |
    v
[12.3 Taxas medidas e intervalos]
    |
    v
[12.4 Taxas de base]
    |
    v
[Síntese]
    |
    v
[Exemplo resolvido] --> [Exercício EX023]

Objetivos de aprendizagem

Você vai (1) calcular probabilidades de eventos independentes e contagens esperadas; (2) raciocinar sobre probabilidades de falha muito pequenas; (3) usar intervalos de confiança para taxas medidas; e (4) interpretar os números de falha de decifração dos esquemas pós-quânticos.

12.1 Eventos raros em escala

Se um evento tem probabilidade p por tentativa e há N tentativas independentes, o número esperado de ocorrências é Np, e a probabilidade de pelo menos uma é 1 − (1 − p)^N ≈ Np quando Np é pequeno. Essa fórmula simples explica por que os criptógrafos exigem probabilidades de falha astronomicamente pequenas. Uma taxa de falha de 2^−20 parece minúscula, mas em 10^9 handshakes ela prevê cerca de 950 falhas. O ML-KEM é projetado para que o desencapsulamento honesto falhe com probabilidade de cerca de 2^−139 no ML-KEM-512 e de cerca de 2^−165 no ML-KEM-768, segundo a análise da FIPS 203, então as falhas são desprezíveis em qualquer escala realista.

12.2 Atividade prática — Laboratório P

# Lab P (ch 12): how small must a failure probability be? Binomial reasoning for rare events.
import math
for p_exp in (-20, -40, -139):
    p = 10.0 ** (p_exp * math.log10(2))       # p = 2^p_exp
    for n_ops in (1e9, 1e15):
        exp_fail = n_ops * p
        print(f"p = 2^{p_exp:5d}, {n_ops:.0e} operations -> expected failures {exp_fail:.3e}")

Saída esperada:

p = 2^  -20, 1e+09 operations -> expected failures 9.537e+02
p = 2^  -20, 1e+15 operations -> expected failures 9.537e+08
p = 2^  -40, 1e+09 operations -> expected failures 9.095e-04
p = 2^  -40, 1e+15 operations -> expected failures 9.095e+02
p = 2^ -139, 1e+09 operations -> expected failures 1.435e-33
p = 2^ -139, 1e+15 operations -> expected failures 1.435e-27

Observe como cada mudança de 20 bits no expoente desloca a contagem esperada por um fator de cerca de um milhão.

As linhas do meio mostram por que as probabilidades de falha nas normas são tão pequenas. Uma taxa que parece desprezível para um bilhão de operações pode produzir centenas de falhas em um milhão de bilhões, que os grandes serviços alcançam ao longo da sua vida. As últimas linhas mostram uma probabilidade tão pequena que não se esperam falhas em nenhuma escala realista. Quando um projeto cita uma taxa de falha, multiplique-a pelo número de operações que você espera antes de decidir se ela importa.

12.3 Taxas medidas e intervalos

Os dados operacionais dão contagens, não probabilidades. Se 3 de 5.000 conexões de teste falham, a estimativa pontual é 0,06%, mas a taxa verdadeira pode ser maior. Um intervalo de confiança de 95% — por exemplo, o intervalo de Wilson usado no Capítulo 29 — expressa essa incerteza. Com amostras pequenas, o limite superior é o que importa para uma decisão de seguir ou não: "estamos razoavelmente confiantes de que a taxa de falha está abaixo de u" é a afirmação defensável.

Relate o intervalo junto com a contagem e o tamanho da amostra, para que o leitor possa julgá-lo.

12.4 Taxas de base

A probabilidade também protege contra alarmes enganosos. Se um detector sinaliza os handshakes que "parecem tentativas de rebaixamento" com 99% de sensibilidade e 1% de falsos positivos, mas as tentativas reais de rebaixamento ocorrem em um handshake por milhão, então quase todos os alertas são falsos. Pergunte sempre pela taxa de base antes de interpretar uma contagem de alertas.

Neste exemplo, um milhão de handshakes daria cerca de dez mil alertas falsos e aproximadamente um verdadeiro. Uma equipe que recebesse esse fluxo aprenderia a ignorar o alerta, o que anula o seu propósito. Detectores melhores, ou a aplicação da regra apenas onde os rebaixamentos são mais prováveis, aumentam a parcela de alertas verdadeiros. A HCU pede esses números antes de adotar qualquer nova regra de detecção.

12.5 Exemplo resolvido

O aplicativo móvel da HCU realiza 2 × 10^8 estabelecimentos de chave por ano. Se um esquema hipotético falhasse com probabilidade 2^−40, as falhas esperadas seriam 2 × 10^8 × 9,1 × 10^−13 ≈ 1,8 × 10^−4 por ano — desprezíveis. Se um bug de implementação elevasse a taxa para 1 em 10^5, a contagem esperada seria de 2.000 por ano, visível nos chamados de suporte. As taxas de falha medidas testam, portanto, a implementação, e não a matemática.

Pediu-se à equipe de suporte da HCU que observasse esse padrão durante o piloto híbrido. Um aumento repentino dos erros de conexão após a atualização de uma biblioteca apontaria para o código, já que a própria taxa de falha do esquema não consegue produzir esses números.

12.6 Erros comuns e limites

Ler a estimativa pontual de uma amostra pequena como a taxa verdadeira.
Ignorar as taxas de base ao interpretar alertas.
Supor independência onde as falhas são correlacionadas (um middlebox ruim afeta todas as conexões que passam por ele).

Amostras pequenas podem produzir uma estimativa pontual muito distante da taxa verdadeira, sobretudo para eventos raros; relate o intervalo. As taxas de base decidem se um alerta provavelmente é real. As falhas correlacionadas, como muitas conexões passando por um único dispositivo defeituoso, quebram a independência que os modelos simples supõem, então as falhas se agrupam e as médias enganam. Verifique onde as falhas ocorrem antes de tratá-las como independentes.

Exercícios

EX023 — Falhas esperadas. Com p = 2^−30 e 10^12 operações, calcule o número esperado de falhas. Rubrica: 3 = ≈ 931, com o método mostrado.
EX024 — Taxa de base. Para o detector de rebaixamento de 12.4, estime a fração de alertas verdadeiros entre 10^8 handshakes. Rubrica: 3 = cerca de 100 verdadeiros em cerca de 10^6 alertas (≈ 0,01%), com o método mostrado.

Síntese

Contagens esperadas, limites de confiança e taxas de base transformam probabilidades minúsculas e dados operacionais ruidosos em decisões defensáveis.