Chapter 12 — Probability and statistics
Lesson map
Lesson 12 published. Map, example, EX023.
flowchart TD
N0["Learning outcomes"]
N1["12.1 Rare events at scale"]
N2["12.2 Practical activity — Lab P"]
N3["12.3 Measured rates and intervals"]
N4["12.4 Base rates"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5
N5 --> EX["Worked example"]
EX --> Q["Exercise EX023"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["12.1 Rare events at scale"]
N2["12.2 Practical activity — Lab P"]
N3["12.3 Measured rates and intervals"]
N4["12.4 Base rates"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX023"]
[Learning outcomes]
|
v
[12.1 Rare events at scale]
|
v
[12.2 Practical activity — Lab P]
|
v
[12.3 Measured rates and intervals]
|
v
[12.4 Base rates]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX023]
Learning outcomes
You will (1) compute probabilities of independent events and expected counts; (2) reason about very small failure probabilities; (3) use confidence intervals for measured rates; and (4) interpret decryption-failure figures in post-quantum schemes.
12.1 Rare events at scale
If an event has probability p per trial and there are N independent trials, the expected number of occurrences is Np, and the probability of at least one is 1 − (1 − p)^N ≈ Np when Np is small. This simple formula explains why cryptographers demand astronomically small failure probabilities. A 2^−20 failure rate sounds tiny, yet across 10^9 handshakes it predicts about 950 failures. ML-KEM is designed so that honest decapsulation fails with probability of about 2^−139 for ML-KEM-512 and about 2^−165 for ML-KEM-768 per FIPS 203's analysis, so failures are negligible at any realistic scale.
12.2 Practical activity — Lab 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}")
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
Notice how each 20-bit change in the exponent shifts the expected count by a factor of about a million.
The middle rows show why failure probabilities in standards are so small. A rate that looks negligible for a billion operations may produce hundreds of failures at a million billion, which large services reach over their lifetime. The last rows show a probability so small that failures are not expected at any realistic scale. When a design quotes a failure rate, multiply it by the number of operations you expect before deciding whether it matters.
12.3 Measured rates and intervals
Operational data gives counts, not probabilities. If 3 of 5,000 test connections fail, the point estimate is 0.06 %, but the true rate could be higher. A 95 % confidence interval — for example the Wilson interval used in Chapter 29 — expresses that uncertainty. With small samples, the upper bound is what matters for a go/no-go decision: "we are fairly confident the failure rate is below u" is the defensible statement.
Report the interval with the count and the sample size, so the reader can judge it.
12.4 Base rates
Probability also protects against misleading alarms. If a detector flags handshakes that "look like downgrade attempts" with 99 % sensitivity and 1 % false positives, but real downgrade attempts occur in one handshake per million, then almost every alert is false. Always ask for the base rate before interpreting an alert count.
In this example, a million handshakes would give about ten thousand false alerts and roughly one true one. A team receiving that stream would learn to ignore the alert, which defeats its purpose. Better detectors, or applying the rule only where downgrades are more likely, raise the share of true alerts. HCU asks for these figures before adopting any new detection rule.
12.5 Worked example
HCU's mobile app performs 2 × 10^8 key establishments per year. If a hypothetical scheme failed with probability 2^−40, expected failures would be 2 × 10^8 × 9.1 × 10^−13 ≈ 1.8 × 10^−4 per year — negligible. If an implementation bug raised the rate to 1 in 10^5, the expected count would be 2,000 per year, visible in support tickets. Measured failure rates therefore test the implementation, not the mathematics.
HCU's support team was asked to watch for this pattern during the hybrid pilot. A sudden rise in connection errors after a library update would point to the code, since the scheme's own failure rate cannot produce such numbers.
12.6 Common errors and limits
- Reading a point estimate from a small sample as the true rate.
- Ignoring base rates when interpreting alerts.
- Assuming independence where failures are correlated (one bad middlebox affects every connection through it).
Small samples can produce a point estimate far from the true rate, especially for rare events; report the interval. Base rates decide whether an alert is likely to be real. Correlated failures, such as many connections passing through one faulty device, break the independence that simple models assume, so failures cluster and averages mislead. Check where failures occur before treating them as independent.
Exercises
- EX023 — Expected failures. With p = 2^−30 and 10^12 operations, compute the expected number of failures. Rubric: 3 = ≈ 931 with method shown.
- EX024 — Base rate. For the downgrade detector in 12.4, estimate the fraction of alerts that are true among 10^8 handshakes. Rubric: 3 = about 100 true of about 10^6 alerts (≈ 0.01 %), method shown.
Synthesis
Expected counts, confidence bounds and base rates turn tiny probabilities and noisy operational data into defensible decisions.
Continue studying — chapter 12 of 40
← Chapter 11 (draft) · Course chapter index · Chapter 13 (draft) →