Chapter 7 — Probability and statistics
Lesson map
Lesson 07 published. Map, example, EX013.
flowchart TD
N0["Learning outcomes"]
N1["7.1 Rare events"]
N2["7.2 Practical activity — Lab P"]
N3["7.3 Confidence intervals"]
N4["7.4 Statistical versus cryptographic security"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5
N5 --> EX["Worked example"]
EX --> Q["Exercise EX013"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["7.1 Rare events"]
N2["7.2 Practical activity — Lab P"]
N3["7.3 Confidence intervals"]
N4["7.4 Statistical versus cryptographic security"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX013"]
[Learning outcomes]
|
v
[7.1 Rare events]
|
v
[7.2 Practical activity — Lab P]
|
v
[7.3 Confidence intervals]
|
v
[7.4 Statistical versus cryptographic security]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX013]
Learning outcomes
You will (1) reason about rare events such as decryption failures; (2) estimate rates with confidence intervals; (3) distinguish statistical from cryptographic security levels; and (4) design a measurement with enough samples. It builds on Chapters 1 and 6 and supports measurement (Chapter 29) and validation (Chapter 38).
7.1 Rare events
Lattice KEMs have a tiny probability that decapsulation produces the wrong key. FIPS 203's parameter sets keep it extremely small — around 2^-139 for ML-KEM-512 and smaller for the larger sets — far below any rate an engineer will observe. The expected number of failures in N operations is N·p. Lab P shows why a probability like 2^-20, fine for many engineering purposes, would be unacceptable for a KEM used billions of times, while 2^-139 is negligible at any scale.
The decision rule is simple: multiply by the largest number of operations the system will ever perform and check that the product stays far below one.
7.2 Practical activity — Lab P
# Lab P (ch 7): 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}")
Expected output:
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
Read the six lines in pairs. At 2^-20, a billion operations already produce nearly a thousand expected failures, so such a scheme would fail visibly every day at BPA's scale. At 2^-40, a billion operations look safe, but a quadrillion, roughly the global volume of a widely deployed protocol over some years, gives about 900. At 2^-139 even the larger count leaves an expected 1.4 × 10^-27, which is why decryption failure is not a design concern for ML-KEM at all. Extend the loop with 1e18 operations and confirm the conclusion does not change.
7.3 Confidence intervals
When measuring handshake failure rates after enabling a hybrid group, report an interval, not just a point. For small proportions use the Wilson interval (Chapter 37's canary lab uses it). The rule of three gives a quick bound: if zero failures occur in n trials, the 95% upper bound on the rate is about 3/n.
The rule follows from requiring that zero failures in n trials has at most a 5% chance: (1 − p)^n = 0.05 gives p ≈ 3/n. It holds only when trials are independent; failures caused by one broken proxy cluster at one site, so a canary spread across several sites gives a more honest bound than the same count from one.
7.4 Statistical versus cryptographic security
A statistical test that finds no failures in a million runs says only that the rate is probably below 3 × 10^-6. Cryptographic security levels such as 2^-128 cannot be established by testing; they come from analysis. Engineers test to find bugs, not to prove security.
To show a rate below 2^-128 by testing, one would need around 10^39 trials, far beyond any computer. Tests are still worth running, because an implementation bug usually produces failures at a rate of one in a few hundred or thousand, which a modest test campaign catches quickly. A clean test run therefore rules out gross bugs while leaving the security claim to the published analysis.
7.5 Worked example
BPA's pilot sees 0 handshake failures in 12,000 hybrid connections at one site. The rule of three bounds the failure rate below 2.5 × 10^-4 (95%). Is that good enough to roll out to 2 million daily connections? At the bound, up to 500 failures per day could still occur — so the gate needs a larger canary before full rollout.
To bring the bound down to about one failure per day at 2 million connections, the rate must be shown below 5 × 10^-7, which by the rule of three needs about 6 million clean connections. BPA can reach that by widening the canary to several sites for a few days, which also tests different middleboxes.
7.6 Common errors and limits
- "No failures observed" interpreted as "rate is zero".
- Confusing a decryption-failure probability with a security level.
- Ignoring that operations multiply: rare per event is not rare per year.
The first error leads teams to declare success after a small pilot, as in the worked example where zero failures in 12,000 still allowed 500 a day. The second confuses two numbers: ML-KEM's 2^-139 failure probability is a reliability figure, while category 3 describes the work an attacker needs. The third is fixed by multiplying per-event rates by annual volume before judging them.
Exercises
- EX013 — Rule of three. How many failure-free trials are needed to bound a rate below 10^-5? Rubric: 3 = 300,000 with reasoning.
- EX014 — Scale. If a component fails with probability 2^-30 per operation and BPA runs 10^10 operations a year, how many failures are expected? Rubric: 3 = ≈ 9.3 and interpretation.
Synthesis
Rare events become common at scale; testing bounds rates but cannot establish cryptographic security; report intervals, and size samples to the decision being made.
Continue studying — chapter 07 of 50
← Chapter 06 (draft) · Course chapter index · Chapter 08 (draft) →