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 (Ω, Pr) where
Ω is a nonempty finite set, called the sample space,
and
| ∑ ω ∈ Ω Pr [ω] = 1 . |
An element
An event is a subset
| Pr [A] = ∑ ω ∈ A Pr [ω], |
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 (Ω, Pr) 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 Pr [ω] lies in [0, 1] and the total is 1 by
normalisation; an event’s probability is a partial sum of nonnegative
terms, hence lies in [0, 1] . For (2), the sets A and
The distribution used most often in cryptography is the uniform distribution.
Let S be a nonempty finite set. The uniform distribution on
S is the probability space (S, Pr) with
| Pr [A] = | A | | S | . |
Conditioning updates the probability of one event on the information that another has occurred.
Let
| Pr [A ∣ B] = Pr [A ∩ B] Pr [B] . |
When
Conditioning on B restricts the sample space to B and
renormalises so that B has probability 1 : the map
Let
| Pr [A 1 ∩ ⋯ ∩ A n] = Pr [A 1] Pr [A 2 ∣ A 1] Pr [A 3 ∣ A 1 ∩ A 2] ⋯ Pr [A n ∣ A 1 ∩ ⋯ ∩ A n − 1] . |
Moreover, if
| Pr [A] = ∑ i = 1 k Pr [A ∣ B i] Pr [B i] . |
The chain rule follows by telescoping: each factor
Independence is the formal statement that one event carries no information about another.
Two events
| Pr [A ∩ B] = Pr [A] Pr [B] . |
A family { A i } i ∈ I of events is mutually
independent if for every finite subset
| Pr [⋂ i ∈ J A i] = ∏ i ∈ J Pr [A i] . |
When
Let (Ω, Pr) be a finite probability space and T any set.
A ( T -valued) random variable is a function
| Pr [X = t] = Pr [{ ω ∈ Ω : X (ω) = t }], |
and more generally
Random variables
| Pr [X 1 = t 1, ..., X n = t n] = ∏ i = 1 n Pr [X i = t i] . |
Let
| E [X] = ∑ ω ∈ Ω X (ω) Pr [ω] = ∑ t ∈ im (X) t ⋅ Pr [X = t], |
where im (X) denotes the (finite) image of X . The two expressions agree by grouping outcomes according to their X -value.
For an event A , its indicator random variable
For any event A ,
By 11.11,
Let
| E [a X + b Y] = a E [X] + b E [Y] . |
More generally, for random variables
| E [∑ i = 1 n a i X i] = ∑ i = 1 n a i E [X i] . |
This holds whether or not the X i are independent.
Directly from the definition,
| E [a X + b Y] | = ∑ ω ∈ Ω (a X (ω) + b Y (ω)) Pr [ω] | ||
| = a ∑ ω X (ω) Pr [ω] + b ∑ ω Y (ω) Pr [ω] | |||
| = a E [X] + b E [Y], |
splitting the finite sum and extracting the constants. The n -term statement follows by induction on n . □
The following consequence underlies every averaging (“heavy-row”) argument in the series.
Let
Every outcome contributes nonnegatively to E [X] , 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 N uniform samples from a set of size N , two are likely to coincide. The birthday bound sets the output lengths of cryptographic hash functions.
For any events
| Pr [⋃ i = 1 n A i] ≤ ∑ i = 1 n Pr [A i] . |
Disjointify the union into “first occurrence” events:
| Pr [⋃ i A i] = Pr [⋃ i B i] = ∑ i Pr [B i] ≤ ∑ i Pr [A i] . ∎ |
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 A i holds except with probability at most
ε i (that is,
| Pr [⋂ i = 1 n A i] ≥ 1 − ∑ i = 1 n ε i . |
By De Morgan,
Sample
| Pr [C] ≤ (k 2) 1 N = k (k − 1) 2 N, |
and, on the other side,
| Pr [C] = 1 − ∏ i = 0 k − 1 (1 − i N) ≥ 1 − e − k (k − 1) / (2 N) . |
In particular a collision becomes likely once
Upper bound. For
Lower bound. The complement C ̄ is the event that
all k samples are distinct. If
| Pr [C ̄] = ∏ i = 0 k − 1 (1 − i N) ≤ ∏ i = 0 k − 1 e − i / N = exp (− 1 N ∑ i = 0 k − 1 i) = e − k (k − 1) / (2 N), |
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 P and Q be probability distributions on the same finite
set S (i.e. probability mass functions
| Δ (P, Q) = 1 2 ∑ s ∈ S | P (s) − Q (s) | . |
For random variables
The factor 1 2 makes Δ range over [0, 1] 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 f applied to a sample,
(1) Nonnegativity holds termwise. For the upper bound, split S into
(2) Symmetry holds termwise. For the triangle inequality,
(3) With D as above, take
(4) First take f deterministic,
| Δ (f (P), f (Q)) = 1 2 ∑ u | P (f − 1 (u)) − Q (f − 1 (u)) | ≤ 1 2 ∑ u ∑ s ∈ f − 1 (u) | P (s) − Q (s) | = Δ (P, Q), |
using
Part (3) states that Δ (P, Q) is exactly the best advantage of
any test — even a computationally unbounded one — that, given a
single sample, must guess whether it came from P or Q : the
optimal test outputs “ P ” 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 Z / q Z (2), a field
element of F p (6), a point in a group. If
the target set S has
Let
| Δ (R, U q) ≤ q K = q 2 L . |
Consequently, if
Write
| Pr [R = r] = { (m + 1) / K, r < t, m / K, r ≥ t . |
Comparing with the target probability 1 / q and using
| | Pr [R = r] − 1 q | ≤ m + 1 K − m K = 1 K for every r . |
Therefore
| Δ (R, U q) = 1 2 ∑ r = 0 q − 1 | Pr [R = r] − 1 q | ≤ 1 2 ⋅ q ⋅ 1 K = q 2 K ≤ q K . |
(The computation yields the sharper bound q / (2 K) ;
q / K 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 (Ω, Pr) in
which Ω is a countable set and
Let (Ω, Pr) be a countable probability space and
| Pr [⋃ n ≥ 1 A n] = ∑ n ≥ 1 Pr [A n], |
and in particular the basic axioms of 11.3 hold unchanged.
Every outcome of the union lies in exactly one A n , so both sides sum the same nonnegative terms Pr [ω] , grouped differently; a series of nonnegative terms may be summed in any order, or in groups, without changing its value. □
Let Pr 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
| Pr [⋃ n ≥ 1 A n] = lim n → ∞ Pr [A n], |
and dually
Disjointify by telescoping: set
| Pr [⋃ n A n] = ∑ n ≥ 1 Pr [D n] = lim n → ∞ ∑ k = 1 n Pr [D k] = lim n → ∞ Pr [A n], |
the final step by finite additivity. The decreasing case follows by complementation. □
Fix a finite outcome set T and a distribution p on T . An
infinite sequence of independent trials with law p 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 —
N (t) of 11.44, or the count X of
11.51, each event “count
A real-valued random quantity X has density
| Pr [a ≤ X ≤ b] = ∫ a b f (t) d t for all a ≤ b ; |
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 T be a random variable with values in
Expanding
In an infinite sequence of independent trials, each succeeding with
probability
The event
Let
| E [∑ i = 1 T X i] = E [T] ⋅ E [X 1] . |
Write
Expanding each
| E [S] = ∑ s s ∑ k ≥ 1 Pr [T = k, S k = s] = ∑ k ≥ 1 E [S k 1 T = k], |
each inner expectation living on the finite prefix space of the first k trials (11.30), where linearity (11.14) expands it as ∑ i = 1 k E [X i 1 T = k] . Regrouping the nonnegative double series once more,
| E [S] = ∑ i ≥ 1 ∑ k ≥ i E [X i 1 T = k] . |
Fix i and let
| ∑ k = i n E [X i 1 T = k] = E [X i 1 T ≥ i] − E [X i 1 T > n] . |
The trials take finitely many values, so
The remaining step is a factorisation. The event
| E [X i 1 T ≥ i] = ∑ t 1, ..., t i g (t 1, ..., t i − 1) t i p (t 1) ⋯ p (t i) = Pr [T ≥ i] ⋅ E [X 1], |
the double sum factoring into the sum over
(t 1, ..., t i − 1) , which totals
| E [S] = ∑ i ≥ 1 E [X 1] Pr [T ≥ i] = E [X 1] ⋅ E [T] . ∎ |
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 c L blocks while the honest chain found L , 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 X is exponential with rate
Let
| Pr [X > s + t ∣ X > s] = Pr [X > t] for all s, t ≥ 0, |
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 1 , and
| E [X] = ∫ 0 ∞ t λ e − λ t d t = [− t e − λ t] 0 ∞ + ∫ 0 ∞ e − λ t d t = 1 λ . |
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 ε T / λ , and for integer-valued T
| Pr [ε T / λ > t] = Pr [T ≥ ⌊ λ t / ε ⌋ + 1] = (1 − ε) ⌊ λ t / ε ⌋ ⟶ e − λ t (ε → 0), |
because
A wallet that must poll each of n 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 U be a density-defined quantity, with density f U , that
is a function of the first k members of an independent family
| Pr [(U, W) ∈ R] = ∫ − ∞ ∞ f U (s) Pr [W ∈ R s] d s, R s = { w : (s, w) ∈ R }, |
the inner probability being a joint event of
Integrate the product density over the first k coordinates
first, holding w fixed: the result is the probability that U
lies in the interval
Let
For
| Pr [a ≤ U + V ≤ b] = ∫ 0 ∞ f U (u) ∫ max (a − u, 0) max (b − u, 0) f V (v) d v d u = ∫ 0 ∞ f U (u) ∫ max (a, u) max (b, u) f V (x − u) d x d u, |
substituting
Let
| Pr [X < Y, X ≤ u] = λ λ + μ (1 − e − (λ + μ) u), |
symmetrically with the roles of (X, λ) and (Y, μ)
exchanged, and
| Pr [X < Y, min (X, Y) ≤ u] = Pr [X < Y] ⋅ Pr [min (X, Y) ≤ u] for all u ≥ 0 . |
The event is the region
| Pr [X < Y, X ≤ u] = ∫ 0 u λ e − λ s Pr [Y > s] d s = ∫ 0 u λ e − (λ + μ) s d s = λ λ + μ (1 − e − (λ + μ) u) . |
The diagonal
An exponential clock of rate λ — a Poisson
process, by 11.47 — is
an independent family
The n -th arrival time S n of an exponential clock of rate
λ has density
Induction on n : f 1 is the exponential density, and
| f n + 1 (s) = ∫ 0 s λ n u n − 1 e − λ u (n − 1) ! λ e − λ (s − u) d u = λ n + 1 e − λ s (n − 1) ! ∫ 0 s u n − 1 d u = λ n + 1 s n e − λ s n ! . ∎ |
A random variable K with values in N 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 N (t) above and the count X of
11.51 below. Let
X be a variable with values in
| E [X] = ∑ x ≥ 0 x Pr [X = x], |
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
| Pr [N (t) = n] = e − λ t (λ t) n n !, n = 0, 1, 2, ... |
In particular N (t) is finite with probability 1 and
For
| Pr [N (t) = n] = ∫ 0 t λ n s n − 1 e − λ s (n − 1) ! Pr [G n + 1 > t − s] d s = λ n e − λ t (n − 1) ! ∫ 0 t s n − 1 d s = e − λ t (λ t) n n ! . |
The event
Markov’s inequality applied to X itself gives a bound decaying only like 1 / a ; applied to e t X , it gives a bound decaying exponentially, with the free parameter t optimised for the threshold. This is the Chernoff method.
For a real-valued random variable X 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:
| M X (t) = ∑ x e t x Pr [X = x] ∈ (0, ∞], |
the sum running over the finite values of X ; its terms are positive,
so
it either converges or is + ∞ . On a countable space it is
E [e t X] , the expectation regrouped by value, and
Let X be as above, a real, and
| Pr [X ≥ a] ≤ e − t a M X (t), |
and hence
The events
Let K be Poisson with mean ν and let
| Pr [K ≥ a] ≤ e a − ν (ν a) a . |
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
X be the number of adversary arrivals strictly before the
L -th honest arrival, for a fixed
| Pr [X = m] = (m + L − 1 m) p L q m, p = λ λ + μ, q = μ λ + μ, m = 0, 1, 2, ..., |
of mean
| M X (t) = (λ λ + μ − μ e t) L ; |
with the honest rate normalised to 1 this is
Write S L for the L -th honest arrival time, a function of
the honest gaps with the density f L of
11.45, and N A for the adversary’s
arrival count. The event
| Pr [X = m] | = ∫ 0 ∞ f L (s) Pr [N A (s) = m] d s = λ L μ m (L − 1) ! m ! ∫ 0 ∞ s m + L − 1 e − (λ + μ) s d s | ||
| = λ L μ m (L − 1) ! m ! ⋅ (m + L − 1) ! (λ + μ) m + L, |
using
For the generating function, set
| (1 − x) T L + 1 (n) = T L (n) − (n + L n) x n + 1 . |
Hence
The same law arises without clocks. In an infinite sequence of
independent trials (11.30) succeeding with
probability p , the number of failures strictly before the
L -th success equals m exactly when the
In the setting of 11.51 with honest rate
1 and adversary rate μ , for every
| Pr [X ≥ c L] ≤ [(1 + c 1 + μ) 1 + c (μ c) c] L, |
the Chernoff bound optimised at
The count X is finite with probability one with values in N
(11.51) and has a law countably additive over
its values (11.31), so
11.49 applies: with
11.51,
| φ ′ (t) = − c + μ e t 1 + μ − μ e t, φ ′′ (t) = μ e t (1 + μ) (1 + μ − μ e t) 2 > 0, |
so φ ′ is strictly increasing (positive derivative) and
vanishes at most once, namely where
With the honest rate 1 , the arrival count X has mean
μ L , the same as the Poisson variable of
11.50 with
| L exact tail clock bound Poisson expression 40 5.05 ⋅ 10 − 2 2.53 ⋅ 10 − 1 1.15 ⋅ 10 − 1 200 1.09 ⋅ 10 − 4 1.04 ⋅ 10 − 3 2.00 ⋅ 10 − 5 400 8.23 ⋅ 10 − 8 1.08 ⋅ 10 − 6 4.00 ⋅ 10 − 10 |
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 N (or a cofinite subset of it) to the nonnegative reals R ≥ 0 , and “for sufficiently large n ” means “for all n beyond some threshold n 0 ”.
Let
The “ = ” in “
The polynomial
Let
Choose witnesses (c 1, n 1) and (c 2, n 2) for the two
hypotheses and let
Fix a distinguished variable
A function
A function f is exponential if
A function
| ν (λ) < 1 λ c for all λ ≥ λ 0 . |
Equivalently,
The functions 2 − λ , 2 − λ , and
λ − log λ are negligible. For 2 − λ :
given any c , the product
Let
If
Summing p (λ) 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 λ − c , 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 c . 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 p (λ) times
(polynomially many, the most an efficient adversary can afford), the
probability that some repetition succeeds is, by the union bound, at
most p (λ) ν (λ) — 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 { 0, 1 } ∗ for the set of all
finite binary strings and | x | for the length of
An algorithm M runs in (deterministic) polynomial time if
there is a polynomial p 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 M 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 poly (λ) 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 A the probability that A solves it is negligible in λ :
| Pr [A solves the task on parameter λ] = negl (λ), |
where the probability is over the task’s randomness and A ’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 { G λ } of order q (λ) asserts: for every PPT A ,
| Pr [A (g, g x) = x] = negl (λ), |
the probability taken over a uniformly chosen generator g of
G λ , 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 poly (λ) ; in a generic discrete-log instantiation one commonly chooses a group order near 2 2 λ ;
the running time of honest algorithms, which must be poly (λ) ; and
the security level: every PPT adversary’s advantage must be negl (λ) .
Passing 1 λ (a string of λ ones, of length
λ ) rather than the integer λ in binary (length
log 2 λ ) 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
poly (λ) 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 2 128 operations; it is an attack estimate, not a theorem about every possible algorithm.