Discrete Math › Section D · Counting › Topic D.11

Probability in algorithms and security

Computers use randomness on purpose: to sort quickly, to test huge numbers for primality, to estimate quantities and to make keys that attackers cannot guess. The counting and expectation tools of this section explain why these methods work and how far to trust them.

Randomness as a tool

An algorithm is usually imagined as a fixed recipe that gives the same output every time. A randomised algorithm is allowed to flip coins as it runs. That sounds like a step backwards, but it often buys speed, simplicity or protection against worst-case inputs. Randomness also sits at the heart of security, where secrets must be unpredictable, and at the heart of hashing, where collisions must be understood rather than wished away. This topic applies three ideas from earlier in the section: the complement rule from "Counting and probability", linearity of expectation from "Random variables and expected value", and the pigeonhole principle.

The birthday problem and hash collisions

How many people are needed before a shared birthday is more likely than not? Assuming 365 equally likely birthdays, the complement rule gives the probability that 23 people all differ as \(\frac{365 \cdot 364 \cdots 343}{365^{23}} \approx 0.493\), so a match has probability about 0.507. The same arithmetic governs a hash function with \(N\) equally likely outputs. With \(k\) inputs there are \(\binom{k}{2}\) pairs, each colliding with probability \(\frac{1}{N}\), so the expected number of colliding pairs is \(\binom{k}{2}/N\). That passes 1 once \(k\) is roughly \(\sqrt{2N}\). Collisions become likely after about \(\sqrt{N}\) inputs, far fewer than \(N\).

Worked example: a 32-bit hash

A system tags records with a 32-bit hash, so \(N = 2^{32} \approx 4.29\) billion possible tags. It stores 100,000 records. 1. Pairs of records: \(\binom{100{,}000}{2} \approx 5.0 \times 10^9\). 2. Expected colliding pairs: \(\frac{5.0 \times 10^9}{4.29 \times 10^9} \approx 1.16\). 3. So, on average, more than one pair of records shares a tag, although the table has over 40,000 tags for every record. 4. A standard approximation puts the chance of at least one collision at about \(1 - e^{-1.16} \approx 0.69\). 5. The conclusion: a 32-bit hash cannot serve as a unique identifier at this scale. Doubling the length to 64 bits pushes the danger zone out to about \(2^{32}\) records.

Las Vegas and Monte Carlo algorithms

Randomised algorithms come in two kinds. A Las Vegas algorithm always returns a correct answer, but its running time is random. Quicksort with a randomly chosen pivot is the standard example: it always sorts correctly, its expected running time is \(O(n \log n)\) on every input, and the \(O(n^2)\) worst case needs a run of very unlucky pivots. A Monte Carlo algorithm runs within a fixed time bound but may return a wrong answer with small probability. The trade-off is chosen to suit the job. A sorting routine must never be wrong; a test that is wrong once in \(10^{24}\) runs is, in practice, perfectly acceptable.

Worked example: shrinking the error

Suppose a Monte Carlo test that says "composite" is always right, but on a composite input it wrongly says "probably prime" with probability at most \(\frac{1}{2}\), independently each run. 1. Run it 20 times. A composite input fools all 20 runs with probability at most \(\left(\frac{1}{2}\right)^{20} \approx 9.5 \times 10^{-7}\), under one in a million. 2. The error shrinks exponentially, while the work grows only linearly. 3. The Miller-Rabin primality test, used to generate keys for encryption, has a better guarantee: with a random base, a composite number passes one round with probability at most \(\frac{1}{4}\). 4. After 40 independent rounds, a composite survives with probability at most \(4^{-40} \approx 8 \times 10^{-25}\).

Estimating by random sampling

Randomness can also measure. Throw \(n\) random points into the unit square and count those landing inside the quarter circle \(x^2 + y^2 \le 1\). Each point lands inside with probability \(\frac{\pi}{4}\), the quarter circle's area, so 4 times the fraction inside estimates \(\pi\). By linearity, the expected fraction is exactly \(\frac{\pi}{4}\), but any one run misses a little. How much? The fraction is an average of \(n\) independent indicators, each with variance \(p(1 - p)\) where \(p = \frac{\pi}{4}\). Independent variances add, so the average has variance \(\frac{p(1 - p)}{n}\), and the spread shrinks like \(\frac{1}{\sqrt{n}}\): a hundred times more points give ten times more accuracy.

Chebyshev's inequality

For any random variable with mean \(\mu\) and standard deviation \(\sigma > 0\), and any \(k > 0\),

P(|X - \mu| \ge k\sigma) \le \frac{1}{k^2}

So at least \(1 - \frac{1}{k^2}\) of the probability lies within \(k\) standard deviations of the mean: at least 75% within 2, and at least \(\frac{8}{9}\) within 3, for every distribution. For the \(\pi\) estimate with 10,000 points, \(\sigma \approx 4\sqrt{0.1685/10{,}000} \approx 0.016\). Chebyshev with \(k = 3\) guarantees the estimate lands within about 0.049 of \(\pi\) with probability at least \(\frac{8}{9}\). The bound is cautious, since it assumes nothing about shape, but it is always valid.

Measuring password strength

A secret chosen uniformly at random from \(N\) possibilities has \(\log_2 N\) bits of entropy: an attacker needs up to \(N\) guesses, and about \(\frac{N}{2}\) on average. Four words chosen at random from a list of 7,776 give \(7776^4\) passphrases, or \(4\log_2 7776 \approx 4 \times 12.92 \approx 51.7\) bits. Eight characters chosen at random from the 94 printable keyboard symbols give \(8\log_2 94 \approx 52.4\) bits, about the same, but are much harder to remember. The formula applies only to random choice. A password that a person invents, such as a word with a digit added, comes from a far smaller and more predictable set than its length suggests.

Where the randomness comes from

Computers mostly produce pseudorandom numbers: a deterministic algorithm expands a starting value, the seed, into a sequence that passes statistical tests for randomness. That is fine for simulations and games. It is not fine for security, because anyone who learns the seed or enough outputs may predict the rest. Keys, tokens and passwords need a cryptographically secure generator, designed so that past outputs reveal nothing useful about future ones and seeded from unpredictable sources in the operating system. In Python, for instance, the random module is meant for modelling and simulation, while the secrets module is meant for security.

Common mistakes to avoid

First, assuming collisions need about \(N\) items; they become likely after about \(\sqrt{N}\). Second, confusing the guarantees: Las Vegas algorithms are always right with random time, while Monte Carlo algorithms have bounded time and a small chance of error. Third, multiplying error probabilities for runs that are not independent. Fourth, treating Chebyshev's bound as the actual probability; it is a worst-case limit. Fifth, computing entropy for a human-chosen password as if it were random, or using an ordinary pseudorandom generator to create secret keys.

Key takeaways

The expected number of collisions among \(k\) items with \(N\) equally likely values is \(\binom{k}{2}/N\), so collisions appear after about \(\sqrt{N}\) items: 23 people for birthdays. Las Vegas algorithms are always correct with random running time; Monte Carlo algorithms risk a small error, which independent repetition shrinks exponentially, as in Miller-Rabin's \(4^{-40}\). Random sampling estimates quantities with spread shrinking like \(\frac{1}{\sqrt{n}}\), and Chebyshev's inequality bounds deviations for any distribution. Random secrets have \(\log_2 N\) bits of entropy and need a cryptographically secure generator.

Flashcards

Flashcard

Birthday problem

23 people: probability of a shared birthday about 0.507

Complement: all birthdays different.

Test your understanding

Question 1 of 5

A hash function has 1,000,000 equally likely outputs. What is the expected number of colliding pairs among 1,000 inputs?

Question 2 of 5

A Monte Carlo test errs with probability at most 1/3 per independent run. What is the fewest runs that push the chance of being fooled every time below 1/1000?

Question 3 of 5

By Chebyshev's inequality, at least what fraction of any distribution lies within 4 standard deviations of the mean?

Question 4 of 5

A passphrase is three words chosen independently and uniformly from a list of 1,024 words. How many bits of entropy does it have?

Question 5 of 5

Quicksort with random pivots always sorts correctly, but its running time varies from run to run. What kind of algorithm is it?

← Previous topicNext topic →