A deployed signature scheme is typically advertised as offering “128-bit security”. The question this section exists to answer is: what, precisely, does that phrase assert, and about whom? It cannot assert that forgery is impossible. A forger may simply guess the secret key: keys are finite strings, so the guess succeeds with some positive probability, and a forger with astronomical luck wins outright. Any honest guarantee is therefore a statement of probability — a bound on the chance that the forger wins. Nor can it speak of one forger only: a guarantee against yesterday’s attack says nothing about tomorrow’s, so the bound must quantify over every attacker whose resources fall within stated limits. Making the sentence “every efficient forger succeeds with at most a stated probability” precise takes three intertwined languages: the language of probability, which permits reasoning about random keys, random challenges, and the probability that an attack succeeds; the language of asymptotics, which describes how resources and success probabilities scale; and the language of computation, which fixes what an efficient algorithm is and what it means for a problem to be hard. This section develops all three from elementary foundations and closes by cashing the opening cheque: the final subsection states exactly what “128-bit security” asserts, and about whom. The only prerequisites are familiarity with finite sets, sums, and elementary calculus — limits, the exponential function, and, for the closing subsection’s density-defined laws, the improper Riemann integral; everything else is constructed here.
Until the closing subsection, all probability spaces are finite. This is no real restriction for the cryptographic material: keys, messages, group elements, bounded-length messages, and the random coins of an algorithm with a fixed running-time bound live in finite sets, and finite spaces need no measure theory. Unbounded retry loops need the extension below even when they terminate with probability one. The closing subsection (§11.7) then extends the theory by exactly the rungs later volumes need — countable additivity, continuity along monotone events, a waiting-time toolkit, and laws defined by densities — declaring its one measure-theoretic debt in place (Remark 11.31).
The basic object is a finite set of outcomes together with an assignment of weights summing to one.
A finite probability space is a pair where is a nonempty finite set, called the sample space, and is a function, called the probability mass function, satisfying the normalisation condition
An element is an outcome (or elementary event).
An event is a subset . Its probability is
with the convention (an empty sum). The event occurs on outcome if .
Because is finite, every subset is an event. This convenience is worth flagging: on an uncountable sample space the general theory specifies a family of admissible events together with its probability assignment, rather than automatically admitting all subsets; finiteness spares us that machinery, and Remark 11.31 marks the one place this series touches it. The following elementary facts hold, and we use them freely.
For any finite probability space and events :
, , and .
(Complement.) .
(Monotonicity.) If then .
(Inclusion–exclusion for two events.) .
(Finite additivity.) If are pairwise disjoint then .
Every claim follows by manipulating the defining sums. For (1), each summand lies in and the total is by normalisation; an event’s probability is a partial sum of nonnegative terms, hence lies in . For (2), the sets and partition , so . For (3), splitting the sum over gives , the second term being a sum of nonnegative numbers. For (5), disjointness means each in the union lies in exactly one , so the double sum counts each exactly once. For (4), write (disjoint), so by (5) ; also , giving . Substituting yields the claim. □
The single most important example, ubiquitous in cryptography, is the uniform distribution.
Let be a nonempty finite set. The uniform distribution on is the probability space with for every . The notation (or ) means that is sampled according to the uniform distribution on . Under the uniform distribution, for any event ,
Thus, for uniform sampling, probability is exactly the ratio of favourable outcomes to total outcomes, recovering the classical counting notion of probability.
Frequently we learn that one event has occurred and must update the probability of another accordingly. Conditioning captures this.
Let be events with . The conditional probability of given is
When the quantity is left undefined.
Conditioning on restricts the sample space to and renormalises so that has probability : the map is itself a probability mass function on , and is the probability it assigns to . Two immediate and indispensable consequences follow.
Let be events with . Then
Moreover, if partition (pairwise disjoint with union ) and each , then for any event ,
The chain rule follows by telescoping: each factor equals by 11.5, and the product collapses to . (Monotonicity ensures that all the intermediate intersections have positive probability, so every factor is defined.) For total probability, the events are pairwise disjoint with union (since the partition ), so finite additivity and give . □
Independence is the formal statement that one event carries no information about another.
Two events are independent if
A family of events is mutually independent if for every finite subset ,
When , independence of and is equivalent to : conditioning on does not change the probability of . Mutual independence is strictly stronger than pairwise independence. The standard counterexample: toss two fair coins, and let be “the first is heads”, “the second is heads”, and “the two coins differ”. Each pair is independent, yet , so the three are not mutually independent.
A random variable assigns a value to each outcome; it summarises a random experiment by a number (or a vector, a string, a group element).
Let be a finite probability space and any set. A (-valued) random variable is a function . When , we call real-valued. For ,
and more generally denotes the probability that takes a value in . The function on the finite image of is the distribution (or law) of .
Random variables (with values in sets ) are mutually independent if for all ,
Let be a real-valued random variable on a finite space. Its expectation (or mean) is
where denotes the (finite) image of . The two expressions agree by grouping outcomes according to their -value.
A frequently used bridge between the two notions is the following: the expectation of the indicator of an event is exactly its probability.
For an event , its indicator random variable takes the value if and otherwise.
For any event , .
By 11.11, , since the indicator vanishes off . □
The principal property of expectation is its linearity, which holds with no independence assumption whatsoever; this absence of any independence hypothesis is what makes expectation so much more tractable than probability.
Let be random variables on a finite space and . Then
More generally, for random variables and scalars ,
This holds whether or not the are independent.
Directly from the definition,
splitting the finite sum and extracting the constants. The -term statement follows by induction on . □
A one-line consequence converts an expectation bound into a probability bound; it underlies every averaging (“heavy-row”) argument in the series.
Let be a real-valued random variable and . Then .
Every outcome contributes nonnegatively to , and each outcome with contributes at least ; hence . □
The payoff of this subsection, stated up front, is the square-root law that sets the output lengths of cryptographic hash functions: among roughly uniform samples from a set of size , two are likely to coincide, so an -bit hash resists collision-finding only up to about work, and output lengths are chosen twice the desired security level. The engine of the calculation is the most frequently used inequality in cryptographic proofs: the union bound. It is crude, it requires no independence, and it almost always suffices.
For any events in a finite probability space,
Disjointify the union into “first occurrence” events: and for . The are pairwise disjoint, , and . By finite additivity and monotonicity (11.3),
The disjointification device — replacing events by pairwise disjoint pieces with the same union — recurs throughout the section: the “first occurrence” form above proves the union bound, and a telescoping form for increasing chains proves the continuity theorem of §11.7. In each case it turns a subadditivity or limit claim into an exact additivity computation. The complementary inequality for conjunctions is equally useful and follows by taking complements.
If each event holds except with probability at most (that is, ), then all of them hold simultaneously except with probability at most :
By De Morgan, . Apply the union bound to the complements and take the complement of both sides. □
We now derive the birthday bound, which governs how soon collisions appear when sampling uniformly.
Sample independently and uniformly from a set of size , and let be the event that some two of them collide, i.e. for some . Then
and, on the other side,
In particular a collision becomes likely once .
Upper bound. For let be the event . Since and are independent and uniform, . Now , a union of events, one per two-element subset of the indices (6.12), so the union bound (11.16) gives .
Lower bound. The complement is the event that all samples are distinct. If , the pigeonhole principle forces a collision, so ; the product also vanishes, through its factor , so the stated equality holds and the exponential bound is trivial. Let then , and for let be the event that the first samples are pairwise distinct (, and ). We show by induction on ; every factor is positive, since , so in particular each has positive probability and conditioning on it is legitimate (11.5). For the step, the events pinning the first samples to specific distinct values partition , each with probability by independence and uniformity; given any one of them, the next sample avoids the values taken with probability , again by independence and uniformity. Averaging over the cells (total probability, 11.6) gives , and completes the induction. Taking yields the stated equality, in which every factor is nonnegative, so the inequality applies factor by factor. (For this inequality follows from Bernoulli’s inequality, for , by letting in the limit definition of ; for the left side is nonpositive.) Thus
summing the exponents via . Taking complements gives . □
With and — the classical birthday party — the exact product gives , already a majority chance, and the proposition brackets it as . The threshold is visible at small scale too: with , the fifth sample (just past ) tips the odds, at .
The threshold is the reason an -bit hash function (so ) offers only about collision resistance: an adversary expects a collision after roughly random evaluations — for , that is . For this reason one chooses output lengths twice the desired security level. The same square-root phenomenon recurs in random-walk discrete-log attacks (Pollard’s rho, 10.30), so designers size the curves used in Halo 2 and Orchard so that is itself astronomically large.
Comparing distributions — for example a real key-generation procedure against an idealised uniform one — requires a notion of how far apart two distributions are. The appropriate notion for “no statistical test can distinguish them well” is statistical distance.
Let and be probability distributions on the same finite set (i.e. probability mass functions ). Their statistical distance (or total variation distance) is
For random variables with values in , denotes the statistical distance of their distributions.
The factor makes range over and gives it a clean interpretation as the maximum advantage of a distinguisher, which part (3) of the next theorem establishes.
Let be distributions on a finite set . Then:
; and if and only if .
(Metric.) is symmetric and satisfies the triangle inequality .
(Variational characterisation.) , where .
(Data processing / post-processing.) For any (possibly randomised) function applied to a sample, . In particular no algorithm can increase statistical distance.
(1) Nonnegativity is clear. For the upper bound, split into and . Since , we have , so . Hence . As , we get . If then every , so ; the converse is immediate.
(2) Symmetry is evident. For the triangle inequality, termwise by the triangle inequality on ; summing over and halving gives the claim.
(3) With as above, take : then , so the maximum is at least . Conversely, for any , , since dropping the negative terms only increases the sum and extending from to all of increases it further. Thus the maximum over of is exactly ; replacing by its complement swaps the sign, giving the same value for .
(4) First take deterministic, . For , . Then
using on each fibre, and that the fibres partition . A randomised is a deterministic function of the sample together with independent fresh coins ; apply the deterministic case to the joint variable , noting that the two joint distributions and have the same statistical distance , the shared coin distribution contributing nothing. □
Part (3) states that is exactly the best advantage of any test — even a computationally unbounded one — that, given a single sample, must guess whether it came from or : the optimal test outputs “” on the set , and its advantage equals . Part (4) is what makes statistical distance compose in proofs: applying the same procedure to two close inputs keeps the outputs close. If , then and are interchangeable in any analysis at the cost of an additive in every probability. When is negligible (11.61 below), we call and statistically indistinguishable.
Cryptography requires uniform elements of finite sets throughout: a uniform scalar in (2), a uniform field element of (6), a uniform point in a group. The most tractable source of randomness, however, is a stream of independent uniform bits. We must therefore convert uniform bitstrings into uniform elements of a target set , and we must understand the bias the conversion introduces.
If is a power of two, the conversion is exact: read uniform bits as a number in and index into . The nontrivial case arises when is not a power of two — most importantly when for a prime , the scalar field of an elliptic curve (10). A common and elementary method is reduce-modulo: sample a long uniform integer and reduce it mod . The result is not perfectly uniform — some residues receive one more preimage than others — but the bias is negligible provided the integer is long enough. The next proposition makes this precise.
Let be an integer and let for a nonnegative integer . Sample uniformly from (equivalently, read uniform bits as an integer), and set . Let denote the uniform distribution on . Then the statistical distance of from uniform satisfies
Consequently, if and one takes bits, then .
Write with and remainder , so . For a residue , the number of integers in congruent to modulo is if and if . Hence
Comparing with the target probability and using (since ),
Therefore
(The computation actually yields the sharper bound ; is the usual stated form.) For the final claim, and give . □
Reduce uniform bits modulo . Here , so the four residues receive preimages each and the residue receives ; the statistical distance from uniform works out to exactly , within the guarantee of the proposition (as and ).
The consequence to remember: to sample a scalar mod a -bit prime with statistical distance below from uniform, draw uniform bits and reduce. The bias , with the slack set to the security parameter, is negligible (11.61), so the reduce-modulo sample is statistically indistinguishable from a perfectly uniform scalar, and by the data-processing inequality (11.22(4)) substituting one for the other anywhere costs at most per use. An alternative, rejection sampling — draw bits, accept if the result is , else retry — gives exactly uniform output at the cost of a variable but (with overwhelming probability) small number of retries; for this series’ purposes the negligible bias of reduce-modulo is acceptable and simpler to analyse. The Orchard specification employs exactly this reduce-modulo sampling when deriving scalars from hash outputs: its reduces the full -bit output modulo the -bit group order — a slack of bits, comfortably beyond the of the worked example (Zcash protocol specification §4.2.3 and §5.4.2).
Everything so far lives on a finite sample space, and for the cryptographic material of the upper volumes that is enough: keys, challenges, and transcripts are finite strings. Two uses need more. A process watched for as long as it takes — a random walk pursued until it first hits a barrier — has no finite horizon, and a waiting time measured in continuous units has no finite sample space at all. This subsection extends the finite theory by exactly the rungs those uses require: countable additivity, continuity along monotone events, a toolkit for waiting times under stopping rules, laws defined by densities, and a toolkit of clocks and tail bounds built on them.
A countable probability space is a pair in which is a countable set and satisfies ; the sum is independent of the enumeration order because its terms are nonnegative. Events are arbitrary subsets , with , and Definitions 11.2–11.11 carry over with “finite” read as “countable” (a random variable’s image may now be countably infinite), with one exception: 11.4 does not — equal weights cannot sum to on a countably infinite set, so the uniform distribution remains a strictly finite notion. Expectation additionally requires its defining sum to converge absolutely.
Let be a countable probability space and pairwise disjoint events. Then
and in particular the basic axioms of 11.3 hold unchanged.
Every outcome of the union lies in exactly one , so both sides sum the same nonnegative terms , grouped differently; a series of nonnegative terms may be summed in any order, or in groups, without changing its value. □
The free regrouping of nonnegative series invoked here — reorder, regroup, exchange double sums, recount by multiplicity — is the workhorse of every infinite-space argument in this subsection: it proves countable additivity above, the tail-sum formula below (where each term is counted by its multiplicity), and the exchange step in Wald’s identity.
Let be a probability assignment, on any sample space, defined for a family of events closed under complement and countable union, and countably additive on it. If is an increasing chain of events, then
and dually for a decreasing chain . On a countable space the hypothesis holds automatically, by 11.28.
Disjointify by telescoping: set and for . The are pairwise disjoint, , and . Countable additivity gives
the final step by finite additivity. The decreasing case follows by complementation. □
Fix a finite outcome set and a distribution on . An infinite sequence of independent trials with law is a sequence of random variables such that every prefix consists of mutually independent -distributed trials in the sense of 11.10 — equivalently, the prefix’s law is that of the finite probability space carrying the product weights . An event is finitely determined if membership in it is decided by some fixed finite prefix; its probability is the finite-space value. An event of the form “some prefix satisfies ” is the union of an increasing chain of finitely determined events, and 11.29 assigns it the limit of the prefix probabilities.
11.30 presumes that a single, countably additive probability assignment on infinite sequences exists that restricts correctly to every finite prefix at once. That existence statement is the Kolmogorov extension theorem, and its proof belongs to measure theory, which lies off this series’ critical path: the space of infinite sequences over at least two possible outcomes is uncountable, so it escapes 11.27, and the extension specifies the admissible events. We therefore take it — with its countable additivity, hence 11.29 — as a foundation stone rather than a theorem. On infinite-sequence spaces, only finitely determined events and their monotone limits appear in this series, and for those the values are forced by the finite theory together with continuity; the density-defined laws of 11.32 carry the analogous debt, their interval and joint-event probabilities being taken to cohere as the stated integrals. The independent families of 11.40 extend that debt in two ways: joint events of several density-defined quantities are taken to be iterated integrals, in whichever order of integration is convenient — the exchange of order for nonnegative integrands is the Fubini–Tonelli theorem, likewise measure-theoretic — and the gap sequences of 11.44 are infinite families, of which only finite prefixes enter any event this series uses, except through countable unions over the values of an arrival count — of 11.44, or the count of 11.51, each event “count ” being a joint event of finitely many gaps. For any set of values, the event “count ” — among them the event that the count is finite, and the tail events of 11.49 — is taken to have probability , by the countable additivity assumed above.
A real-valued random quantity has density if and
improper Riemann integrals suffice throughout this series. The distribution function is , so , and single points carry probability zero. The expectation is when this integral converges absolutely. Two density-defined quantities are independent if for all intervals ; probabilities of joint events are then taken to factor through iterated integrals of the product .
Waiting times are the extension’s chief dividend. The three short results of this toolkit — used by later volumes’ extractor and race analyses — follow from countable expectation and finitely determined events alone. One convention first: for a variable with values in , the defining sum of the expectation has nonnegative terms, and we permit the value when it diverges.
Let be a random variable with values in and . Then , either side being infinite exactly when the other is.
Expanding and regrouping the doubly indexed nonnegative series, each term is counted once for every , that is, times; nonnegative series may be regrouped freely. □
In an infinite sequence of independent trials, each succeeding with probability , let be the index of the first success. Then and .
The event says the first trials all fail — a finitely determined event of probability ; in particular by continuity (11.29). The tail-sum formula then gives , a geometric series. □
Let be an infinite sequence of independent trials with common law, each with finite mean, and let be a stopping rule: a random index such that, for every , whether is decided by the first trials alone. If , then
Write and , so that on the event . The hypothesis forces , by the convention preceding 11.33. The variable takes countably many values — on it agrees with , whose values run over a finite set, the trials having finitely many outcomes — and each event is the disjoint countable union of finitely determined events, so its probability is assigned by countable additivity (11.31). By we mean , the expectation of this countably supported distribution, a sum of nonnegative terms.
Expanding each and regrouping the doubly indexed nonnegative series,
each inner expectation living on the finite prefix space of the first trials (11.30), where linearity (11.14) expands it as . Regrouping the nonnegative double series once more,
Fix and let . The events (for ), , and are all decided by the first trials, and on that prefix space the pointwise identity holds, so linearity gives
The trials take finitely many values, so for a constant , and as : the terms of the convergent series tend to zero. Hence .
Now the crux factorisation. The event — the negation of — is decided by the first trials, so its indicator is a function of the first trial values, and on the prefix space of the first trials the expectation splits along the product weights of 11.30: with the common law,
the double sum factoring into the sum over , which totals , times . Assembling the pieces and applying the tail-sum formula (11.33),
The second dividend is continuous time. A block-discovery process is modelled by clocks: each party’s next block arrives after a random delay, a delay does not remember how long it has already run, and two parties race. A light client that samples a chain needs a tail bound — how likely is an adversary to have found blocks while the honest chain found ? — and a wallet that spaces its network queries needs a delay law with a prescribed mean and no memory. This unit builds the clocks, counts their arrivals, and proves the tail bounds those uses invoke, in the forms they invoke them. Everything reduces to density-defined laws (11.32), elementary calculus, and Markov’s inequality with a free parameter.
A random quantity is exponential with rate , written , if it has the density for and for .
Let . Then for all , , and
conditional probability being the ratio of 11.5: having waited without an arrival teaches nothing about the remaining wait. Conversely, a nonnegative quantity with for all is exponential with rate .
The density integrates to , and . Integrating by parts,
Since implies , the conditional probability is . For the converse, the events and () differ by , so ; and the point carries probability at most for every , hence zero, so is the same integral. □
The exponential law is the continuous limit of the geometric waiting time (11.34). If trials succeed with a small probability and each occupies time , the first success arrives at time , and for integer-valued
because and the floor alters the exponent by less than one. Whether a proof of work fits this picture — each candidate independent of the last — is a question about the trials, which the volumes on consensus take up.
A wallet that must poll each of addresses about once a day waits between polls, with seconds: by 11.37, one expected poll per address per day. For , seconds, eight hours; the gap exceeds a full day with probability , and exceeds twice its mean with probability whatever is. By memorylessness, an observer who has seen no poll for a while has learnt nothing about when the next one comes.
Two clocks race, and clocks are restarted; both need joint events of several density-defined quantities, which 11.32 provides only for pairs.
Density-defined quantities with densities form an independent family if for all intervals . As in 11.32, the probability of a joint event , for a region cut out by finitely many inequalities, is then taken to be the iterated integral of over , in whichever order of integration is convenient (11.31). In particular a quantity that is a function of one block of the family is independent of a quantity that is a function of a disjoint block: integrate the two blocks separately. A sequence is an independent family if every finite prefix is one, in the manner of 11.30.
Let be a density-defined quantity, with density , that is a function of the first members of an independent family , and write . Let be a region in the -coordinates whose section is an interval for every fixed value of . Then
the inner probability being a joint event of alone.
Integrate the product density over the first coordinates first, holding fixed: the result is the probability that lies in the interval , which by 11.32 equals . What remains is the integral of against this function of ; exchanging the order and integrating over first leaves, for each , the inner probability . □
Let be independent density-defined quantities, nonnegative (their densities vanish on the negative axis). Then is density-defined, with density the convolution for .
For , the event is the region , so
substituting in the inner integral. Exchanging the order, the region becomes , , and the right-hand side is . With and the left-hand side is , so is a density. □
Let and be independent. Then, for every ,
symmetrically with the roles of and exchanged, and . Consequently ; the winning time is exponential with rate ; and the winner is independent of the winning time,
The event is the region , in the -plane. Integrating over first (11.40),
The diagonal has inner integral zero, so , and gives . On the event the winning time is , so the displayed formula is ; adding its mirror for gives , whence is exponential with rate by the characterisation in 11.37, and the formula is exactly the product . Differencing at two values of extends the factorisation from half-lines to intervals. □
An exponential clock of rate — a Poisson process, once 11.47 is in hand — is an independent family of quantities, the gaps. Its arrival times are the partial sums , with , and its arrival count up to time is , the number of arrivals in , a value in that 11.47 shows finite with probability one. The event is , a joint event of the first gaps.
The -th arrival time of an exponential clock of rate has density for .
A random variable with values in is Poisson with mean if for every . The weights sum to by the exponential series , and , so the parameter is indeed the mean.
An arrival count is a function of the gaps of a clock family, so it lives on no finite or countable space, and the expectation of 11.11 does not literally apply to it. One convention serves every such count in this unit — above and the count of 11.51 below. Let be a variable with values in that is a function of the gaps, each event with finite being a joint event of finitely many gaps, with the probability of 11.40. Events , for sets of finite values, have the probabilities (11.31), and when is finite with probability its mean is defined by the law,
a sum of nonnegative terms, permitted to be as in the convention preceding 11.33. On a finite or countable space this sum is the second expression of 11.11, the expectation regrouped by value (11.27), so the two definitions agree whenever both apply.
For an exponential clock of rate and every , the arrival count is Poisson with mean :
In particular is finite with probability and : a rate- clock delivers arrivals per unit time on average.
For the event is , of probability . For the event is, in the -coordinates, the region , , whose section at fixed is the interval ; the quantity is a function of the first gaps with the density of 11.45, so 11.41 gives
The event is the disjoint union of the events , so its probability is the sum of the weights (11.31), which is (11.46); and the mean — the sum over the law, by the convention above — is the one computed in 11.46. □
The tail bounds now. Markov’s inequality applied to itself decays only like ; applied to it decays exponentially, and the free parameter is then tuned to the threshold. That is the whole of the Chernoff method.
For a real-valued random variable with finite or countable image — one on a finite or countable space, or an arrival count of a clock family in the sense of the convention preceding 11.47, restricted to its finite values (the value has probability zero there), whose law is countably additive over its values: for every set of values (11.31) — and a real , the moment generating function is
the sum running over the finite values of ; its terms are positive, so it either converges or is . On a countable space it is , the expectation regrouped by value, and .
Let be as above, real, and with . Then
and hence , the infimum over the at which is finite.
Let be Poisson with mean and let . Then for every real , and
In particular, for and with , the bound reads .
Expanding, . The exponent of the Chernoff bound has and , so it is minimised at , a positive exactly when ; there , with the natural logarithm — base-free is natural throughout, base two being written — and exponentiating gives the bound. Substituting and gives . □
Let two exponential clocks be independent — their gaps together form one independent family — with rates , the honest clock, and , the adversary clock, and let be the number of adversary arrivals strictly before the -th honest arrival, for a fixed . Then is finite with probability , with the negative binomial law
of mean , and, for every real with ,
with the honest rate normalised to this is . Only the ratio enters.
Write for the -th honest arrival time, a function of the honest gaps with the density of 11.45, and for the adversary’s arrival count. The event differs from only on the events and , with the adversary gaps; each of these, in the coordinates , has a single point as its section at fixed adversary gaps, hence probability zero (11.32), so . The latter event is the region , whose section at fixed adversary gaps is an interval. By 11.41 and 11.47,
using for , which integrations by parts establish. Rearranging the factorials gives the binomial coefficient and the powers of and .
For the generating function, set , so that exactly when . Then , and we claim the series is , by induction on . For it is the geometric series. For the step, write for the partial sums. Pascal’s rule — sort the -subsets of items, which the coefficients count (6.12), by whether they contain a distinguished item — gives, on subtracting from term by term,
Hence by the induction hypothesis: the partial sums increase and are bounded, so the series converges, and its terms tend to zero. Letting in the display gives , the claim for . Hence , which is the displayed form after multiplying numerator and denominator by . At this gives ; the event is the disjoint union of the events , so its probability is this sum (11.31), and is finite with probability . For the mean — the sum over the law, by the convention preceding 11.47 — , so by the same series with in place of . □
The same law arises without clocks. In an infinite sequence of independent trials (11.30) succeeding with probability , the number of failures strictly before the -th success equals exactly when the -th trial succeeds and, among the first , precisely fail: orders, one per choice of the failing positions (6.12), each of probability . The two-clock race and memorylessness (11.43 and 11.37) are what identify the clock model’s attribution sequence — which clock fires next — with such a coin sequence of success probability ; later volumes carry out that identification.
In the setting of 11.51 with honest rate and adversary rate , for every ,
the Chernoff bound optimised at . The base in brackets is strictly less than , so the bound decays exponentially in .
The count is finite with probability one with values in (11.51) and has a law countably additive over its values (11.31), so 11.49 applies: with 11.51, with , for . On that interval
so is strictly increasing (positive derivative) and vanishes at most once, namely where , that is, at ; this lies in the interval because gives and gives . Thus decreases before and increases after it, and is its minimum on the interval. At , , so , which is the bracketed base. Finally and decreases on , since , so : the base is below . □
With the honest rate , the arrival count has mean , the same as the Poisson variable of 11.50 with , which counts adversary arrivals in a window of fixed length ; the two laws differ because the window here ends at the random time . Substituting one for the other is tempting and wrong. At and , the exact tail (summing 11.51), the bound of 11.53, and the Poisson expression are
At and the Poisson expression lies below the exact tail, so it is not an upper bound for the arrival count; its base per unit of is , against for the valid bound. A bound stated for the wrong law is not a bound.
Later volumes build block-discovery and extraction analyses directly on this base: block clocks are the exponential clocks above, their races and arrival counts the lemmas of this unit, block-attribution sequences are infinite sequences of independent trials, extractor running times are the waiting times of the previous unit (the geometric waiting time and Wald’s identity), and the limit arguments instantiate 11.29.
The discussion now turns from probability to growth rates. To address efficiency and hardness, we must compare how functions of an integer parameter grow as that parameter tends to infinity. The Bachmann–Landau notation makes such comparisons precise. Throughout, functions map (or a cofinite subset of it) to the nonnegative reals , and “for sufficiently large ” means “for all beyond some threshold ”.
Let with eventually positive.
(read “ is big-O of ”, an asymptotic upper bound) if there exist constants and with for all .
(asymptotic lower bound) if there exist and with for all ; equivalently, if and only if .
(tight bound) if and ; i.e. there are and with for .
(read “little-o”, strictly smaller order) if for every there is with for all ; equivalently .
(strictly larger order) if ; equivalently .
The “” in “” is traditional but denotes set membership: is the class of all functions bounded above by a constant multiple of , and means . One never reads such equations right to left. We follow the customary abuse of notation.
The polynomial is : for one has , with equality on the right at , so the constant is exact there. Also , since ; ; (any polynomial is little-o of any exponential with base ); and . A cautionary pair: is false, but is true, since is within a constant factor.
Let and . Then and . The same closure statements hold with replaced uniformly by or . Moreover is transitive: and imply .
Choose witnesses and for the two hypotheses and let . For , , and , so the two right-hand forms agree up to a constant; this proves the sum rule. For products, . Transitivity: and eventually give eventually. The statements follow by the equivalence , and by combining the two. □
The payoff of this subsection is a closure theorem (11.63): the class of negligible functions — those shrinking faster than the reciprocal of every polynomial — is stable under exactly the operations that security proofs perform, addition and multiplication by polynomials, which is why “negligible” is the right formalisation of “ignorable”. We first classify the growth rates relevant to cryptography. Fix a distinguished variable , the security parameter (discussed in detail in §11.11); informally, larger means more security and larger keys. Resources (running time, key length) and success probabilities are functions of .
A function is polynomially bounded, written , if there is a constant (and a threshold) with for all large ; equivalently, for some constant . It is super-polynomial if it grows faster than every polynomial, i.e. for every constant (equivalently, for all ).
A function is exponential if ; the prototypical case is for a constant . A super-polynomial function with is sub-exponential; examples are and the index-calculus running time in the bit length (7.22). Every exponential function is super-polynomial; the converse fails by these examples.
The central cryptographic notion is that of a negligible function. A negligible probability may be ignored because no efficient (polynomially many) repetition of an experiment can amplify it to a noticeable chance — the closure theorem below makes this precise.
A function is negligible, written , if for every positive constant there exists such that
Equivalently, for every constant ; equivalently, as for every constant . A function is non-negligible if it is not negligible, i.e. for infinitely many , for some constant ; it is noticeable if there exist and with for all (noticeable implies non-negligible, but not conversely); it is overwhelming if is negligible.
The functions , , and are negligible. For : given any , the product tends to (a polynomial over an exponential), meeting the definition. By contrast, is not negligible — taking shows for all — it is noticeable, even though it tends to . This is the key subtlety: tending to zero does not suffice; a negligible function must beat every inverse polynomial.
Let be negligible and let be a polynomially bounded function. Then:
is negligible (the class is closed under addition, hence under any fixed finite sum).
is negligible (a polynomial times a negligible function is negligible).
If for all large , then is negligible (domination by a negligible function).
Summing functions, each bounded by a single negligible function , yields a negligible function; in particular a union bound over polynomially many negligible events is negligible.
The mechanism throughout is an exponent shift: to beat , invoke negligibility at a strictly larger exponent, so that the surplus absorbs the combining factor. The same shift is the standard mechanism behind hybrid and union-bound steps in security proofs.
(1) Fix . Applying the definition at the exponent , there is a threshold beyond which (the latter once ); adding the two bounds gives for all large .
(2) Suppose for large (and some constant ). Fix . By negligibility applied at the exponent , for large , whence for large . Hence is negligible.
(3) Immediate: if eventually and eventually, then eventually, for every .
(4) Write the sum , where each by hypothesis (in security proofs all the arise from one bound). Then , which is negligible by (2); conclude by (3). □
Suppose an adversary wins a game with negligible probability . If it repeats the attack times (polynomially many, the most an efficient adversary can afford), the probability that some repetition succeeds is, by the union bound, at most — still negligible by 11.63(2). Thus negligible success probability remains negligible under any efficient amplification: it is genuinely ignorable. Conversely, a noticeable success probability can be boosted to a constant by repetitions. The negligible/non-negligible split is the formal backbone of the phrase “the scheme is secure except with negligible probability”: security asserts a negligible advantage, and an attack means a non-negligible one. (A merely non-negligible — not noticeable — success probability is boosted to a constant only on the infinitely many where the inverse-polynomial bound holds, which already suffices to contradict a security definition.)
It remains to make “efficient algorithm” and “infeasible” precise. We adopt the standard model: algorithms are Turing machines (equivalently, up to polynomial factors, programs in any reasonable model of computation), inputs and outputs are finite binary strings, and the measured resource is the number of elementary steps as a function of input length. Write for the set of all finite binary strings and for the length of .
An algorithm runs in (deterministic) polynomial time if there is a polynomial such that, on every input , halts within at most steps and produces an output. The class of decision problems solvable by such machines is .
Determinism is insufficient for cryptography: key generation and sampling require randomness. We model randomness by granting the machine an auxiliary tape of independent uniform random bits (the “coins”).
A probabilistic (or randomised) algorithm is a Turing machine with an additional read-only random tape initialised with independent uniformly random bits . For a fixed input , the output is a random variable over the choice of ; write to display the coins explicitly, and then is a deterministic function. The algorithm runs in probabilistic polynomial time (it is PPT) if there is a polynomial such that, for every input and every choice of coins , halts within steps. (Bounding the time for every , not merely in expectation, is the standard “strict” notion and ensures ever reads only coins.)
There are two standard ways to formalise an efficient adversary. The uniform model is a single PPT machine that works for all input lengths, as above. The non-uniform model allows a separate algorithm (equivalently, a Boolean circuit) of size for each , which may be hard-wired with an arbitrary polynomial-length “advice” string depending on . Non-uniform adversaries are at least as powerful as uniform ones and are often more convenient in reduction proofs, because the advice can encode a “best” attack. The asymptotic theory of this section is identical for both models; security definitions in the Halo 2/Orchard setting typically state security against non-uniform PPT adversaries, the more conservative choice.
With efficiency pinned down, we can state the strong hardness notion used in cryptography. The guiding principle is the Cobham–Edmonds thesis: “efficiently computable” means “computable in polynomial time”. Feasibility and the infeasibility notion below are useful opposite regimes, but they are not logical negations: intermediate success probabilities can fall into neither class.
A computational task parameterised by the security parameter is (computationally) feasible if there is a PPT algorithm solving it with overwhelming success probability. It is infeasible if for every PPT algorithm the probability that solves it is negligible in :
where the probability is over the task’s randomness and ’s coins. Equivalently: no efficient algorithm succeeds with non-negligible probability.
Cryptographic assumptions are infeasibility statements. For instance, the discrete-logarithm assumption in a family of groups of order asserts: for every PPT ,
the probability taken over a uniformly chosen generator of , a uniform , and ’s coins. The entire edifice of Halo 2 and Orchard rests on such asymptotic infeasibility assumptions; choosing a parameter size does not prove them. Separately, concrete analysis asks how much work the best known attacks need at one fixed size. Generic discrete-log attacks take group operations by the birthday/rho phenomenon of 11.20; absent a faster structure-specific attack, an order near therefore targets about bits of generic-group security. The Pasta orders are just above , giving roughly generic work. The asymptotic language permits the terms “negligible” and “polynomial”; concrete estimates remain conditional on the attacks presently known.
The section closes by making explicit the parameter that threads through every preceding definition, and by paying its opening debt.
The security parameter is a positive integer supplied to all algorithms of a cryptographic scheme, conventionally in unary as the string (so that “polynomial in the input length” coincides with “polynomial in ”). It governs simultaneously:
the sizes of objects — key lengths and encodings, each ; in a generic discrete-log instantiation one commonly chooses a group order near ;
the running time of honest algorithms, which must be ; and
the security level: every PPT adversary’s advantage must be .
Passing (a string of ones, of length ) rather than the integer in binary (length ) is a deliberate convention: it forces “polynomial time in the input length” to mean polynomial in itself, so an honest key generator may take time to produce -bit keys. In a scheme satisfying the security definition, increasing raises honest cost only polynomially while every PPT adversary’s success remains negligible; in common concrete families, the best known attack cost grows exponentially. Asymptotic security is the statement that this gap holds for all sufficiently large ; the practitioner then fixes a single value (commonly , targeting -operation attacks) and checks the concrete estimates against that target — the just-over- Pallas/Vesta group orders give roughly generic group operations (10; Zcash protocol specification §5.4.9.6), hash outputs of bits per the birthday bound of 11.18, and sampling slack of at least extra bits per 11.24 (the deployed of 11.26 reduces bits, a slack of ). Every “negligible” in the remainder of the series is implicitly a function of this .
The opening cheque can now be cashed, with its two layers kept separate. Asymptotic infeasibility (11.68) quantifies over every probabilistic polynomial-time forger — uniform or hard-wired with advice (11.67) — and requires its success to be negligible in , a bound that no polynomial number of repetitions amplifies to a noticeable chance (11.64). A concrete “128-bit” estimate instead says that the best known applicable attack at a fixed parameter size costs on the order of operations; it is an attack estimate, not a theorem about every possible algorithm. Pasta’s just-over- group orders give roughly generic group operations and are conventionally placed near that target. The forger of the opening paragraph may still guess a key and win with astronomical luck; the formal promise is negligible success against every PPT forger, conditional on the stated cryptographic assumptions.