This section fixes the language of security claims: probability, asymptotic notation, and efficient computation. It proves the union and birthday bounds, the properties of statistical distance, the bias bound for modular reduction, Wald’s identity, Chernoff bounds for the arrival counts of exponential clocks, and the closure of negligible functions under addition and multiplication by polynomials. The birthday bound sets hash output lengths, and the bias bound justifies the sampling of Orchard scalars; later volumes build their block-discovery and extraction analyses on the waiting-time and clock results. A signature scheme advertised as offering “128-bit security” cannot exclude forgery: a forger that guesses the secret key, a finite string, succeeds with positive probability, so the claim bounds the success probability of every attacker within stated resources; §11.11 states what it asserts. Probability spaces are finite until §11.7; finite spaces suffice for keys, bounded-length messages, group elements, and the coins of an algorithm with a fixed running-time bound. The prerequisites are finite sets, sums, and elementary calculus: limits, the exponential function, and, for the density-defined laws of §11.7, the improper Riemann integral.
A finite probability space is a pair where
is a nonempty finite set, called the sample space,
and
An element
An event is a subset
with the convention
Because is finite, every subset is an event. On an uncountable sample space the general theory specifies a family of admissible events together with its probability assignment; Remark 11.31 marks the one place this series requires measure theory. The following facts are used without further citation.
For any finite probability space and events
(Complement.)
(Monotonicity.) If
(Inclusion–exclusion for two events.)
(Finite additivity.) If
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
The distribution used most often in cryptography is the uniform distribution.
Let be a nonempty finite set. The uniform distribution on
is the probability space with
Conditioning updates the probability of one event on the information that another has occurred.
Let
When
Conditioning on restricts the sample space to and
renormalises so that has probability : the map
Let
Moreover, if
The chain rule follows by telescoping: each factor
Independence is the formal statement that one event carries no information about another.
Two events
A family of events is mutually
independent if for every finite subset
When
Let be a finite probability space and any set.
A (-valued) random variable is a function
and more generally
Random variables
Let
where denotes the (finite) image of . The two expressions agree by grouping outcomes according to their -value.
For an event , its indicator random variable
For any event ,
By 11.11,
Let
More generally, for random variables
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 . □
The following consequence underlies every averaging (“heavy-row”) argument in the series.
Let
Every outcome contributes nonnegatively to , and each outcome
with
This subsection proves the union bound, the inequality used most often in cryptographic proofs; it requires no independence. It gives the upper half of the birthday bound, which governs how soon collisions appear under uniform sampling: among roughly uniform samples from a set of size , two are likely to coincide. The birthday bound sets the output lengths of cryptographic hash functions.
For any events
Disjointify the union into “first occurrence” events:
The “first occurrence” disjointification recurs, in a telescoping form for increasing chains, in the proof of the continuity theorem of §11.7. Taking complements in the union bound gives the corresponding inequality for conjunctions.
If each event holds except with probability at most
(that is,
By De Morgan,
Sample
and, on the other side,
In particular a collision becomes likely once
Upper bound. For
Lower bound. The complement is the event that
all samples are distinct. If
summing the exponents via
With
The threshold
Statistical distance measures how far apart two distributions are, such as a real key-generation procedure and an idealised uniform one; it formalises “no statistical test can distinguish them well”.
Let and be probability distributions on the same finite
set (i.e. probability mass functions
For random variables
The factor makes range over and makes it equal to the maximum advantage of a distinguisher, as part (3) of the next theorem establishes.
Let
(Metric.) is symmetric and satisfies the
triangle inequality
(Variational characterisation.)
(Data processing / post-processing.) For any (possibly
randomised) function applied to a sample,
(1) Nonnegativity holds termwise. For the upper bound, split into
(2) Symmetry holds termwise. For the triangle inequality,
(3) With as above, take
(4) First take deterministic,
using
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
The most tractable source of randomness is a stream of independent
uniform bits, whereas cryptography requires uniform elements of other
finite sets: a scalar in (2), a field
element of (6), a point in a group. If
the target set has
Let
Consequently, if
Write
Comparing with the target probability and using
Therefore
(The computation yields the sharper bound ;
is the usual stated form.) For the final claim,
Let
By the proposition, a scalar modulo a
Two uses require more than a finite sample space. A process observed until an event occurs, such as an unbounded retry loop or a random walk run until it first hits a barrier, has no finite horizon, even when it terminates with probability one; a waiting time measured in continuous units has no finite sample space. This subsection adds countable additivity, continuity along monotone events, and laws defined by densities, and states in Remark 11.31 the measure-theoretic results it assumes.
A countable probability space is a pair in
which is a countable set and
Let be a countable probability space and
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. □
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
and dually
Disjointify by telescoping: set
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
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. This series therefore takes
it, with its countable additivity and hence
11.29, as an assumption 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 determined by the finite theory together with continuity;
the density-defined laws of 11.32 rest on the
analogous assumption, their interval and joint-event probabilities
being taken to cohere as the stated integrals. The independent
families of 11.40 extend that
assumption 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
A real-valued random quantity has density
improper Riemann integrals suffice throughout this series. The
distribution function is
The results of this unit need only countable expectation and finitely
determined events. For a variable with values in
Let be a random variable with values in
Expanding
In an infinite sequence of independent trials, each succeeding with
probability
The event
Let
Write
Expanding each
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 trials take finitely many values, so
The remaining step is a factorisation. The event
the double sum factoring into the sum over
, which totals
Block discovery is modelled by clocks: each party’s next block arrives after a random delay whose remaining law does not depend on how long the delay has already run, and two parties race. A light client that samples a chain needs a tail bound on the probability that an adversary has 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 constructs these clocks and proves the tail bounds from density-defined laws (11.32) and Markov’s inequality with a free parameter.
A random quantity is exponential with rate
Let
conditional probability being the ratio of
11.5: a wait without an arrival leaves the law
of the remaining wait unchanged. Conversely, a nonnegative quantity
with
The density integrates to , and
Since
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
A wallet that must poll each of addresses about once a day
waits
Clock races and clock restarts both involve joint events of several density-defined quantities, which 11.32 provides only for pairs.
Density-defined quantities
Let be a density-defined quantity, with density , that
is a function of the first members of an independent family
the inner probability being a joint event of
Integrate the product density over the first coordinates
first, holding fixed: the result is the probability that
lies in the interval
Let
For
substituting
Let
symmetrically with the roles of and
exchanged, and
The event is the region
The diagonal
An exponential clock of rate — a Poisson
process, by 11.47 — is
an independent family
The -th arrival time of an exponential clock of rate
has density
A random variable with values in is Poisson with
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. The
following convention covers above and the count of
11.51 below. Let
be a variable with values in
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
In particular is finite with probability and
For
The event
Markov’s inequality applied to itself gives a bound decaying only like ; applied to , it gives a bound decaying exponentially, with the free parameter optimised for the threshold. This is 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:
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
and hence
Let be Poisson with mean and let
In particular, for
Expanding,
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
of mean
with the honest rate normalised to this is
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
using
For the generating function, set
Hence
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
In the setting of 11.51 with honest rate
and adversary rate , for every
the Chernoff bound optimised at
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,
so is strictly increasing (positive derivative) and
vanishes at most once, namely where
With the honest rate , the arrival count has mean
, the same as the Poisson variable of
11.50 with
At
Later volumes build block-discovery and extraction analyses on these results: 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.
Efficiency and hardness are stated by comparing how functions of an integer parameter grow as that parameter tends to infinity, in the Bachmann–Landau notation. Throughout, functions map (or a cofinite subset of it) to the nonnegative reals , and “for sufficiently large ” means “for all beyond some threshold ”.
Let
The “” in “
The polynomial
Let
Choose witnesses and for the two
hypotheses and let
Fix a distinguished variable
A function
A function is exponential if
A function
Equivalently,
The functions , , and
are negligible. For :
given any , the product
Let
If
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 proof rests on an exponent shift: to obtain a bound below , negligibility is invoked at a strictly larger exponent, so that the surplus absorbs the combining factor. The same shift underlies the hybrid and union-bound steps of security proofs.
(1) Fix . Applying the definition at the exponent
(2) Suppose
(3) Immediate: if
(4) Write the sum
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, and
may therefore be ignored. Conversely, a noticeable success probability
This subsection makes “efficient algorithm” and “infeasible”
precise in 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
Key generation and sampling require randomness, which a probabilistic algorithm reads from an auxiliary tape of independent uniform random bits, its “coins”.
A probabilistic (or randomised) algorithm is a
Turing machine with an additional read-only random tape
initialised with independent uniformly random bits
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.
The hardness notion below rests on the Cobham–Edmonds thesis: “efficiently computable” means “computable in polynomial time”. Feasibility and infeasibility are opposite regimes but 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
This subsection fixes the parameter in which negligibility, efficiency, and infeasibility are measured, and states what the “128-bit security” claim of the section opening asserts.
The security parameter is a positive integer
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
The “128-bit security” claim of the section opening has two separate layers. Asymptotic infeasibility (11.68) requires the success probability of every probabilistic polynomial-time forger, uniform or hard-wired with advice (11.67), to be negligible in , a bound that no polynomial number of repetitions amplifies to a noticeable probability (11.64); it holds conditionally on the stated cryptographic assumptions and does not exclude the positive success probability of a forger that guesses a key. A concrete “128-bit” estimate states 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.