This section makes “the scheme is secure” a statement with
mathematical content; every later section states its security
definitions and proofs in these terms. It defines the security
parameter and the adversary, indistinguishability of probability
ensembles, security games and advantage, reductions and their loss, the
standard and random oracle models, and concrete n -bit security, and
proves the hierarchy of indistinguishability notions
(Proposition 1.10) and the hybrid lemma
(Lemma 1.13). A security claim is a universally
quantified statement about a precisely delimited class of adversaries;
the groups, fields and curves of the Math Guide carry no
security guarantee by themselves. Unconditional proofs of security are
almost never available, since one would typically imply
The vocabulary of efficiency is that of the closing section of the Math Guide, recalled here with the refinements cryptography needs.
The security parameter
Schemes are families because security is asymptotic: no scheme with a
fixed finite key length is unbreakable, since an adversary with enough
time enumerates a finite key space. The requirement is that, as
λ grows, the costs of the honest parties (key generation,
encryption, signing) grow polynomially while the cost of the best
attack grows super-polynomially, ideally exponentially; security is a
statement about the limit
The unary encoding replaces the ⌈ log 2 λ ⌉ -bit binary representation of λ because complexity theory measures running time as a function of input length: in binary, of length Θ (log λ) , the parameter would allow an algorithm polynomial in its input length only poly (log λ) steps—too few to write down a λ -bit key. The convention is a normalisation only; no substantive result depends on it.
Every quantity in this volume—the adversary’s success probability, its running time, the key length—is a function of λ , even where the notation suppresses the dependence. A single number—“the advantage is at most 2 − 128 ”—either fixes a concrete λ or describes the function’s behaviour for the λ of interest.
An algorithm A is probabilistic polynomial-time
(PPT) if it is a probabilistic Turing machine—one equipped with a
read-only tape of independent uniformly random bits, its random
tape—and there is a polynomial p such that on every input
x , and for every setting of the random tape, A
halts within p (| x |) steps: the strict, worst-case notion of the
Math Guide (§“Algorithms, running time, and PPT”). We write
Polynomial time. Polynomial time abstracts “feasible computation”: it is closed under composition and invariant across all reasonable deterministic computational models (the strong Church–Turing thesis). The honest parties run in polynomial time so that the scheme is usable; security asserts that no polynomial-time attack succeeds.
Randomness. Honest algorithms need randomness: deterministic encryption leaks whether two ciphertexts encrypt the same message, and key generation must sample secrets unpredictably. The adversary is granted randomness as well, both so that it has the resources of the honest parties and because a deterministic adversary is the special case in which the random tape is ignored.
This volume adopts as standard the non-uniform strengthening that the Math Guide mentions (§“Algorithms, running time, and PPT”).
A non-uniform PPT adversary is a family { A λ } λ ∈ N of probabilistic circuits (or, equivalently, Turing machines each supplied with an advice string z λ of length poly (λ) ) such that a single polynomial in λ bounds the size of A λ . The advice may depend arbitrarily on λ but not on the particular inputs drawn at run time.
The distinction between uniform adversaries (a single machine that reads 1 λ and works for all λ ) and non-uniform ones (a separate circuit per λ , or a uniform machine with per- λ advice) is substantive: non-uniformity grants the adversary free precomputed advice tailored to each parameter size, for example a short hint about the group in use for that parameter. Security against non-uniform adversaries is the stronger and now-standard requirement, partly because non-uniform models compose more cleanly under reduction (one may “hard-wire” a fixed good choice of randomness or auxiliary input). All definitions below can be read in either model; hardness assumptions are stated against non-uniform adversaries where the distinction matters, and the choice is otherwise left implicit.
Two refinements recur. First, some definitions allow expected polynomial-time adversaries, bounding the average rather than worst-case running time; this matters for certain extraction arguments in zero-knowledge, and is flagged where it arises. Second, for post-quantum security one replaces PPT by quantum polynomial-time (QPT)—polynomial-size circuits of quantum gates followed by a measurement, a model this volume does not formalise; the consequences for the assumptions this volume relies on are taken up under “Quantum adversaries: Shor’s algorithm” in the next section. The structural definitions of this section (advantage, indistinguishability, reduction) are agnostic to which class of adversaries one quantifies over; only the underlying hardness assumptions change.
The most basic security goal is that no adversary distinguishes two situations: a real protocol transcript from a simulated one, an encryption of m 0 from an encryption of m 1 , a pseudorandom string from a truly random one. The situations are formalised as ensembles of probability distributions.
A probability ensemble is a sequence
The statistical distance of the Math Guide (§“Statistical distance”) is recalled for countable supports, which ensembles require; the Math Guide treats finite ones.
Let
| Δ (X, Y) := 1 2 ∑ s ∈ S | Pr [X = s] − Pr [Y = s] | . |
For
| Δ (X, Y) = max T ⊆ S (Pr [X ∈ T] − Pr [Y ∈ T]) = max D (Pr [D (X) = 1] − Pr [D (Y) = 1]), |
where the last maximum ranges over all (even computationally
unbounded, deterministic) decision functions
The set form is the variational characterisation in the
statistical-distance theorem of the Math Guide
(§“Statistical distance”), whose argument is unchanged over a
countable S . Only the reformulation over decision functions is
new: a deterministic D is the indicator of the set
The statistical distance is a metric on probability distributions:
| Δ (f (X), f (Y)) ≤ Δ (X, Y) . |
These are the metric and data-processing parts of the statistical-distance theorem of the Math Guide (§“Statistical distance”), again with the argument unchanged over a countable S . □
The grades of indistinguishability below use the asymptotic vocabulary
of the Math Guide (§“Polynomial, exponential, and negligible
functions”). A function
Let
The ensembles X and Y are perfectly
indistinguishable, written
The ensembles X and Y are statistically
indistinguishable, written
| Δ (X λ, Y λ) = negl (λ) . |
The ensembles X and Y are computationally
indistinguishable, written
| Adv X, Y dist (D, λ) := | Pr [D (1 λ, X λ) = 1] − Pr [D (1 λ, Y λ) = 1] | |
is negligible in λ . The probabilities are over the draw from the ensemble and over D ’s internal randomness.
The three notions form a strict hierarchy, whose second strictness
example needs two primitives, defined here in the form the volume uses
throughout. Write U n for the uniform distribution on
{ 0, 1 } n . A one-way function is a polynomial-time
computable
| Pr [h (A (1 λ, h (x))) = h (x)] = negl (λ) (x ← U λ) . |
A pseudorandom generator (PRG) is a polynomial-time computable
For all ensembles
| X ≡ Y ⟹ X ≈ s Y ⟹ X ≈ c Y . |
The first implication is strict: there exist ensembles that are statistically but not perfectly indistinguishable. The second is strict provided one-way functions exist: under that assumption there exist ensembles that are computationally but not statistically indistinguishable.
If
For strictness of the first implication, let X λ be uniform
on { 0, 1 } λ and let Y λ be uniform on
For strictness of the second, assume one-way functions exist; then a
PRG exists—the Håstad–Impagliazzo–Levin–Luby theorem,
together with the routine lemma that extends any stretch to the
doubling one, both used without proof—and furnishes an ensemble:
let G be a PRG, let
In the strictness example the PRG output and a random string are at statistical distance nearly 1 , because the PRG image is a vanishing fraction of the codomain; an unbounded distinguisher checks membership in the image and succeeds. Computational indistinguishability asserts only that finding an efficient test for membership in that image is infeasible. Information-theoretic security with short keys is impossible; computational security, which rests on conjectured hardness, replaces it and permits both public-key primitives and the encryption of long messages under short keys. Statistical and perfect security, when attainable, are unconditional.
Two lemmas make indistinguishability composable: efficient post-processing cannot create a distinguishing advantage, and a polynomially long chain of pairwise-indistinguishable steps cannot accumulate one. The proof of the first is the simplest instance of a reduction.
If
Suppose some PPT distinguisher D separates
{ M (X λ) } from { M (Y λ) } with advantage
δ (λ) . Define
| Adv X, Y dist (D ′, λ) = | Pr [D (M (X λ)) = 1] − Pr [D (M (Y λ)) = 1] | = δ (λ) . |
By
The hybrid argument compares two ensembles connected by a chain of pairwise-close intermediate ensembles. It is the triangle inequality with a refinement that imprecise statements omit: the uniformity hypothesis, which explains why the number of hybrids must be polynomial.
Let
| α i (D, λ) := | Pr [D (H λ i) = 1] − Pr [D (H λ i + 1) = 1] | |
are uniformly negligible: a single negligible function ν
(depending on D ) satisfies
Fix a PPT distinguisher D and let ν be the uniform bound the hypothesis supplies for D . By the triangle inequality applied to the telescoping sum,
| | Pr [D (H λ 0) = 1] − Pr [D (H λ t) = 1] | = | ∑ i = 0 t − 1 (Pr [D (H λ i) = 1] − Pr [D (H λ i + 1) = 1]) | ≤ ∑ i = 0 t − 1 α i (D, λ), |
and the hypothesis bounds the sum by
Uniformity in i is essential, and no argument derives it from the
weaker hypothesis that each α i is negligible for every
fixed i : there the threshold beyond which the i -th term
is small can depend on i , and the dependence cannot be removed.
For a countermodel, take
Applications usually obtain the conclusion by a stronger, structural
route. Suppose the chain arises from a single underlying
assumption
The hybrid argument is where the restriction to “polynomially many” steps is used. A negligible per-step advantage multiplied by a polynomial number of steps remains negligible; a negligible per-step advantage multiplied by, say, 2 λ steps need not. Hence constructions that would require exponentially many hybrids yield no security proof.
The standard formulation expresses a security definition as a game (or experiment) between a challenger and an adversary A : the challenger, following a fixed protocol, sets up the scheme, answers the adversary’s queries, and finally declares the adversary a winner or loser by outputting a single bit.
A security game (or experiment) G is a PPT
interactive algorithm, the challenger, that takes 1 λ ,
interacts with an adversary A , and finally outputs a bit
Distinguishing (indistinguishability) games, where the
challenger secretly chooses a uniform bit
| Adv G (A, λ) := | Pr [G A (λ) = 1] − 1 2 | = 1 2 | Pr [b ′ = 1 ∣ b = 1] − Pr [b ′ = 1 ∣ b = 0] | . |
Trivial guessing achieves winning probability 1 / 2 , hence advantage 0 .
Search (unforgeability/inversion) games, where the adversary must produce a specific kind of object—a forgery, a preimage, a discrete logarithm—and wins iff it succeeds. Here the baseline winning probability is (essentially) 0 , and one sets
| Adv G (A, λ) := Pr [G A (λ) = 1] . |
Figure 1 draws the interaction.
A scheme is secure with respect to the game G if for every PPT adversary A ,
| Adv G (A, λ) = negl (λ) . |
The negligible bound may differ from one adversary to another; the claim is universal over the class. The use of negl on the right makes the definition robust to the polynomial slack that reductions introduce.
The distinguishing game for a pseudorandom generator
The challenger samples
The adversary A outputs a guess b ′ ; the game
outputs 1 iff
The generator is secure iff
Game-based proofs are sequences of games: one rewrites the real
security game through a series of games
A reduction is an efficient transformation that converts a successful adversary against a scheme into a successful algorithm against a problem believed to be hard. Its existence proves the implication “ Π is hard ⇒ X is secure” by establishing the contrapositive “ X is broken ⇒ Π is solved”.
A computational problem Π consists of a PPT instance generator Inst (1 λ) producing a problem instance together with any side information, and a relation deciding when a candidate output solves the instance. The success probability of an algorithm B is
| Succ Π (B, λ) := Pr [B (1 λ, Inst (1 λ)) solves the instance] . |
The problem Π is hard if
Let X be a scheme with security game G X and Π
a computational problem. A (black-box) reduction from breaking
X to solving Π is a PPT oracle algorithm R
with the following per-adversary guarantee: for every
adversary A , writing
| Succ Π (R A, λ) ≥ f (ε X (λ), λ), |
where f is a function fixed by the reduction (not by A ) that maps every non-negligible ε X to a non-negligible bound. The running time of R is measured with each call to A counted as one step, so “PPT” bounds R ’s own work, and hence its number of calls to A , by a polynomial in λ ; the running time of R A is then polynomial whenever A ’s is, however many times R runs A . How far f degrades ε X is the reduction’s loss, discussed below. The reduction is black-box because R uses A only through its input/output interface, making no use of A ’s code.
Every reduction has the same structure. To prove “if Π is hard then X is secure”:
Assume, towards the contrapositive, a PPT adversary A that breaks X with non-negligible advantage ε X .
Construct a PPT algorithm R that, given a random instance of Π , embeds that instance into a simulated security game for A . The simulation must be faithful: the view R presents to A must follow (perfectly, statistically, or computationally) the distribution of the real game, so that A ’s advantage carries over.
Run A . From whatever A does to win its game, R extracts a solution to the Π -instance.
Conclude that R solves Π with non-negligible probability, contradicting the hardness of Π . Therefore no such A exists, and X is secure.
Figure 2 draws this structure.
Let
Suppose A is a PPT adversary that, on input a transcript
(g a, g b) , outputs g a b with probability
The reduction R forms the simulated transcript (A, B) and feeds it to A as the public transcript of G X .
Because (a, b) are uniform in the CDH instance and in the real game, the view of A follows identically the distribution of its view in G X (the simulation is perfect; no loss in faithfulness).
When A outputs a candidate key K , R outputs K as its CDH answer.
Since the simulated and real views are identically distributed,
A outputs
| Succ CDH (R, λ) = ε X (λ) . |
The running time of R is that of A plus a
constant amount of group bookkeeping, hence polynomial. If
ε X were noticeable, R would solve
CDH with noticeable probability, contradicting its
hardness. Therefore ε X (λ) is not noticeable, as
claimed. Moreover, since R is PPT and CDH is
hard (Definition 1.19, search branch),
This reduction is tight: it calls the adversary once and converts advantage ε X into success probability exactly ε X . Most reductions incur a loss, quantified as follows.
Consider a reduction R that transforms an adversary
running in time t with advantage ε into a
Π -solver running in time
| L (λ) := ε / t ε ′ / t ′ = ε ε ′ ⋅ t ′ t, |
the ratio of the solver’s work-per-success to the adversary’s
work-per-success. A reduction is tight if
Asymptotically, loss does not affect the conclusion: a polynomial
loss factor turns a negligible advantage into a negligible advantage
and a hard problem into security. Concretely, however, loss carries a
cost. Suppose a scheme reduces to a problem
believed to offer 128 bits of security, but the reduction loses a factor
A recurrent source of large loss is rewinding: running the
adversary, recording its behaviour, then restarting it from a saved
state with fresh randomness on some branch to obtain a second,
correlated transcript. From two transcripts that share a prefix but
diverge afterwards one can often extract a secret (e.g. two valid
signatures on the same commitment yield the signing key, or two
accepting proof transcripts yield a witness). The forking
lemma, stated as the general forking lemma under “Security in the
random oracle model and the forking lemma”, quantifies the success
probability of obtaining such a pair: if the adversary succeeds with
probability ε after at most q random-oracle queries
whose answers are drawn from a set of size h , the forked run
succeeds with probability at least
The assumptions a proof makes define the model in which it resides. Two models predominate.
A proof resides in the standard model if it assumes only the computational hardness of explicitly stated problems (factoring, discrete logarithm, the decisional Diffie–Hellman problem of the next section, and so on) and grants the adversary no idealised access to any component of the scheme. Every primitive, including every hash function, is a concrete algorithm whose code the adversary may inspect and exploit.
A proof resides in the random oracle model (ROM) if it idealises one or more hash functions as a random oracle: a publicly accessible function O that, on each distinct input, returns an independent, uniformly random output of the appropriate length, consistently answering repeated queries with the same value. The oracle is available to the honest parties, to the adversary, and, in particular, to the reduction. No party holds the “code” of O ; it can only be queried.
Real hash functions are fixed, public algorithms, not truly random functions. The idealisation is adopted because it gives the reduction two capabilities that the standard model withholds and that render many otherwise-intractable proofs tractable.
In the ROM the reduction simulates the oracle for the
adversary. Observability: the reduction sees every query the adversary
makes to O . Since the adversary, to use a hash value
meaningfully, must query it, the reduction learns the adversary’s
intermediate computations—for instance the preimage the adversary is
about to hash. Programmability: the reduction may choose each
oracle answer on the fly, subject only to the answers appearing
uniform and consistent. It can therefore plant its hard-problem
instance inside an oracle response—e.g. set
In the “full domain hash” signature, the signer signs a message
m as
A proof in the ROM is a proof about an idealised model: deploying the scheme instantiates O with a concrete hash function, and the proof does not formally transfer—a ROM proof rules out all attacks that treat the hash as a black box, while offering no guarantee against attacks on the specific structure of the chosen hash. The case for trusting it runs in three steps: prove the scheme secure against a perfect random oracle; instantiate O with a hash believed to have no exploitable structure; and observe that any remaining attack must exploit structure the random oracle lacks, so would be a direct break of the presumed structure-free hash. The gap is nonetheless a theorem: Canetti, Goldreich, and Halevi exhibit contrived schemes provably secure in the ROM yet insecure under every efficiently computable instantiation, so no concrete hash soundly instantiates the oracle for all schemes. No natural deployed scheme is known to be affected; this volume treats a ROM proof as strong positive evidence, not a guarantee, and prefers a standard-model proof when one is available at comparable cost. A quantum adversary (Remark 1.4) queries the oracle in superposition, a single query addressing a weighted combination of all inputs at once; in the resulting quantum random oracle model (QROM) the two powers of Remark 1.27 become subtler and classical ROM theorems do not automatically carry over, so post-quantum claims for arguments made non-interactive by hashing the transcript (the Fiat–Shamir transform, developed under “The Fiat–Shamir transform: from interactive to non-interactive”) must be made in that model.
Further idealisations, between and beyond these two models, are relevant to the proof systems this volume targets. The common reference string (CRS) model posits a trusted public string sampled from a prescribed distribution, used by many succinct proof systems. The generic group model (GGM) idealises the group dual to the manner in which the ROM idealises a hash: the adversary may only perform group operations through an oracle on opaque “handles”, never exploiting the bit representation of group elements; it is the standard setting for lower bounds on discrete-log-type problems. The algebraic group model (AGM) is an intermediate, milder idealisation requiring the adversary to “explain” every group element it outputs as a known combination of its inputs. These models trade realism for provability along the same axis as the ROM; later constructions name the model wherever they require one.
Asymptotic security establishes that a scheme is eventually secure, not whether a deployment with given parameters resists an adversary with a given budget. Concrete (or exact) security settles the latter by explicit bounds on running time and advantage.
Fix the security parameter to a concrete value (so all sizes are
fixed). A scheme is (t, ε) -secure for a game
G if every adversary running in time at most t has
advantage
A scheme (or problem) is commonly said to offer n bits of security when the cheapest known attack achieving constant success probability (say at least 1 2 ) costs on the order of 2 n elementary operations. A proof may justify the stronger, explicit claim that every adversary running in time t has advantage at most about t / 2 n , but that linear advantage bound is not implied merely by the absence of a faster known attack. Thus “ 128 -bit security” is a concrete estimate, relative to a specified attack model and state of knowledge, that breaking the scheme costs roughly 2 128 work.
The security parameter λ is chosen so that the resulting
concrete scheme delivers the desired number of bits of security. In
the cleanest case the two coincide,
For a generic-group or hash-based primitive, doubling the output
length doubles the bit security: a hash with 2 n -bit output offers
n -bit collision resistance—by the birthday bound (Math
Guide, §“The union bound and a birthday calculation”)—and
2 n -bit preimage resistance, so the parameter and the security
level are proportional. For discrete-logarithm-based primitives the
accounting differs. In a group of prime order
The preceding components combine into a parameter-selection
procedure. First, the target security level n is fixed
(commonly 128 ). Second, the underlying hard problem and the cost
of its best attack as a function of the parameter are identified
(e.g. 2 l / 2 for elliptic-curve discrete log), and the
parameter is set so the problem itself offers n bits (here
A proof of security is a proof relative to a model: a definition of the goal (the game), a class of adversaries (PPT, possibly non-uniform or quantum), and a set of assumptions (the hard problems, and any idealisation such as the ROM). It guarantees nothing outside that model: side-channel leakage (timing, power), faulty randomness, implementation bugs, broken assumptions, and goals the game did not capture all lie beyond its reach. The framework does not render schemes unconditionally safe; it renders the conditions of safety explicit, falsifiable, and modular, so that progress on assumptions and attacks translates into recalibrated guarantees. Every construction in this monograph is analysed within this framework.