Every claim this volume makes ends, once unwound, in a sentence about an enemy. No forger produces a valid signature on a message the signer never signed; no observer tells an encryption of from an encryption of ; no prover opens one commitment to two different values. Before any such sentence can be a theorem, the enemy must be a mathematical object: something with a precisely delimited repertoire, about which a universally quantified statement can be proved. The preceding volume supplied the algebraic raw material—groups in which discrete logarithms appear hard, finite fields, elliptic curves—but an object is not yet a guarantee. This section builds the adversary, and around it the framework in which “the scheme is secure” becomes a claim with mathematical content.
The central methodological idea is the following. One almost never knows how to prove unconditionally that a cryptographic scheme is secure; such a proof would typically imply —that problems whose solutions can be checked in polynomial time are not all solvable in polynomial time—and a great deal more. Cryptography therefore adopts a relativised standard of proof. One isolates a small number of computational problems—factoring, discrete logarithm, decisional Diffie–Hellman, and the like—that have resisted decades of attack, and reduces the security of the schemes to the conjectured hardness of those problems. A proof of security is then a proof of an implication: if the underlying problem is hard, then the scheme is secure. Equivalently, in its contrapositive and more operationally useful form: any adversary that breaks the scheme can be mechanically transformed into an algorithm that solves the underlying hard problem. Since no such algorithm is believed to exist, one concludes that no such adversary exists.
To render any of this rigorous, we must pin down four things: what counts as a “scheme”, parametrised by a notion of input size; what counts as an “adversary”; what it means for an adversary to “break” a scheme, measured by a quantity called its advantage; and what it means for one problem to reduce to another. We develop these in turn, followed by the two idealisations under which proofs proceed (the standard model and the random oracle model), and finally the translation between the clean asymptotic language and the concrete “-bit security” numbers that practitioners actually quote.
The vocabulary of efficiency and smallness is the Math Guide’s, fixed in its closing section; we recall it here in the form this volume uses and extend it with the refinements that are specifically cryptographic.
The security parameter is a positive integer that controls the sizes of all objects in a cryptographic scheme—key lengths, group orders, output lengths—and is conventionally supplied to every algorithm in unary, written , the string of ones, so that an algorithm running in time polynomial in the length of its input automatically receives time polynomial in (Math Guide, §“The security parameter”). Every scheme in this monograph is accordingly not a single object but an infinite family of objects indexed by .
Two questions immediately arise: why a family, and why unary.
The reason for a family is that security is inherently asymptotic. There is no such thing as an absolutely unbreakable scheme with fixed finite key length: an adversary with enough time can always enumerate a finite key space. What we can hope for is that as grows, the resources required to break the scheme grow far faster than the resources required to use it. The honest parties’ costs (key generation, encryption, signing) should grow slowly in —polynomially—while the best attack’s cost should grow quickly—super-polynomially, ideally exponentially. The security parameter is the dial that separates these two growth rates, and security is a statement about the limit .
The reason for unary encoding, rather than the -bit binary representation of , is a bookkeeping convenience that aligns two notions of “polynomial time”. Complexity theory measures running time as a function of input length. If came in binary it would have length , and an algorithm “polynomial in its input length” would get only steps—not even enough to write down a -bit key. Padding the parameter to length ensures that “polynomial in the input length” coincides with the cryptographically meaningful “polynomial in ”. This is purely a normalisation; nothing of substance depends on it.
Because everything is indexed by , every quantity we discuss is really a function of : the adversary’s success probability, its running time, the key length. A single number—“the advantage is at most ”—either fixes a concrete or describes the function’s behaviour for the of interest. Keeping the dependence on explicit, at least mentally, prevents nearly every confusion in this subject.
Having fixed how scheme sizes scale, we fix what an attacker may do. An algorithm 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 such that on every input , and for every setting of the random tape, halts within steps: the strict, worst-case notion, exactly as fixed in the Math Guide (§“Algorithms, running time, and PPT”). Write for the random variable obtained by running on with freshly sampled randomness, and for the deterministic output when the random tape is fixed to the string . The honest algorithms and the adversary alike are modelled as PPT machines.
Two of the modelling choices folded into that sentence warrant comment.
Why polynomial time? Polynomial time is the standard mathematical abstraction of “feasible computation”. It is robust—closed under composition, and invariant across all reasonable deterministic computational models (the strong Church–Turing thesis)—which makes it a clean class to quantify over. Crucially, we require the honest parties to run in polynomial time too; a scheme is useful only if it can be used efficiently. The security claim is then an asymmetry between a polynomial-time honest world and a quantified statement that no polynomial-time attack succeeds.
Why probabilistic? Randomness is not a luxury but a necessity in cryptography. Deterministic encryption leaks whether two ciphertexts encrypt the same message; key generation must sample secrets unpredictably. We therefore grant the adversary randomness too, both for fairness and because a deterministic adversary is the special case where the random tape is ignored.
The adversary class itself admits a strengthening that the Math Guide mentions (§“Algorithms, running time, and PPT”) and this volume adopts as standard.
A non-uniform PPT adversary is a family of probabilistic circuits (or, equivalently, Turing machines each supplied with an advice string of length ) such that a single polynomial in bounds the size of . 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 and works for all ) and non-uniform ones (a separate circuit per , or a uniform machine with per- advice) is a genuine one. Non-uniformity grants the adversary free precomputed advice tailored to each parameter size— for example, a short hint about the group of the day. 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 flavour; we state hardness assumptions against non-uniform adversaries when it matters and otherwise leave the choice 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 we flag it 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 “The quantum caveat: 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 thing an adversary can attempt is to tell two situations apart—a real protocol transcript from a simulated one, an encryption of from an encryption of , a pseudorandom string from a truly random one. The most basic security goal is that it cannot. To formalise “look the same” we first formalise the two situations as ensembles of probability distributions, then define three grades of sameness.
A probability ensemble is a sequence of probability distributions (equivalently, random variables), one for each value of the security parameter, where is supported on binary strings whose length is bounded by a polynomial in . There is often an additional index—an input —written ; for clarity we suppress it unless needed.
The natural metric on a single pair of distributions is the statistical distance of the Math Guide (§“Statistical distance”), which we recall in the slightly wider generality this volume needs: supports there are finite, while ensembles as just defined live on countable sets of strings.
Let be discrete random variables over a common finite or countable set . Their statistical distance (or total variation distance) is
For over ,
where the last maximum ranges over all (even computationally unbounded, deterministic) decision functions . In particular, no procedure whatsoever— efficient or not—can distinguish from with advantage exceeding .
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 . Only the reformulation over decision functions is new: a deterministic is the indicator of the set , so the maximum over equals the maximum over ; a randomised is a convex combination of deterministic ones and cannot do better. □
The statistical distance is a metric on probability distributions: , it is symmetric, iff and are identically distributed, and it satisfies the triangle inequality . Moreover it never increases under (possibly randomised) post-processing: for any function—indeed any randomised algorithm—,
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 . □
The weakest of the three grades below needs the asymptotic vocabulary of the Math Guide (§“Polynomial, exponential, and negligible functions”), which we recall in one breath. A function is negligible, written , if for every there exists such that for all —it decays faster than the reciprocal of every polynomial. A function is non-negligible if it is not negligible; it is noticeable if there exists with for all sufficiently large (noticeable functions are non-negligible, but not conversely); it is overwhelming if is negligible. The class of negligible functions is closed under addition and under multiplication by any polynomial—the closure property, proved there, on which the hybrid argument of the next subsection depends.
Let and be probability ensembles.
The ensembles and are perfectly indistinguishable, written , if and are identically distributed for every ; equivalently for all .
The ensembles and are statistically indistinguishable, written , if their statistical distance is negligible:
The ensembles and are computationally indistinguishable, written , if for every PPT algorithm (the distinguisher), the function
is negligible in . The probabilities are over the draw from the ensemble and over ’s internal randomness.
These three notions sit in a strict hierarchy. The implications are immediate from the definitions and the variational characterisation; standard examples witness the strictness. The second example needs two primitives, which we define here in the form the volume uses throughout; write for the uniform distribution on . A one-way function is a polynomial-time computable that no PPT algorithm inverts on a random input: for every PPT ,
A pseudorandom generator (PRG) is a polynomial-time computable whose output on a uniform seed is computationally indistinguishable from uniform, ; the doubling stretch is a normalisation. Whether one-way functions exist is open, which is why the second strictness below is stated conditionally.
For all ensembles :
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 then , which is negligible, so . If , then for any—in particular any PPT—distinguisher , Proposition 1.7 gives , so .
For strictness of the first implication, let be uniform on and let be uniform on . They are not identically distributed (the point has probabilities and ), so not perfectly indistinguishable, yet , so they are statistically indistinguishable.
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 be a PRG, let , and let . By definition of a PRG, . But is supported on at most strings out of , so a set equal to the image of has while ; hence , which is not negligible. Thus but . □
The strictness example is instructive. Statistically the PRG output and a random string are almost as far apart as two distributions can be—distance nearly —because the PRG image is a vanishing fraction of the codomain. An unbounded distinguisher simply checks membership in the image and wins. The entire content of computational indistinguishability is that finding that image membership test is infeasible. This is the bargain at the heart of cryptography: we trade the impossible (information-theoretic security with short keys) for the merely conjectured-hard (computational security), and in exchange we obtain the ability to encrypt long messages under short keys, build public-key primitives, and so on. Statistical and perfect security, when attainable, are unconditional and need no hardness assumption; computational security buys vastly more functionality at the cost of resting on an assumption.
Indistinguishability would be of little use if every application had to be argued from scratch. Two lemmas make it composable: efficient post-processing cannot create a distinguishing edge, and a polynomially long chain of pairwise-indistinguishable steps cannot accumulate one. The first is a reduction in miniature—the template for every reduction in this volume; the second, the hybrid argument, is the workhorse of the entire proof literature.
If and is any PPT algorithm, then the ensembles and satisfy .
Suppose some PPT distinguisher separates from with advantage . Define , i.e. . Since and are both PPT, so is . Then
By the left side is negligible, so is negligible. □
Many proofs must compare two ensembles that are far apart but connected by a chain of pairwise-close intermediate ensembles. The hybrid argument turns such a chain into a single conclusion. It is essentially the triangle inequality, but with a refinement—the uniformity hypothesis—that explains why the number of hybrids must be polynomial and that careless statements omit.
Let be polynomially bounded, and let be a sequence of distributions (the hybrids). Suppose that for every PPT distinguisher the neighbouring advantages
are uniformly negligible: a single negligible function (depending on ) satisfies for all simultaneously. Equivalently, , i.e. is negligible along every index function —arbitrary, not merely efficiently computable, since the maximising index need not be efficient. Then and are computationally indistinguishable, i.e. for every PPT , .
Fix a PPT distinguisher and let be the uniform bound the hypothesis supplies for . By the triangle inequality applied to the telescoping sum,
and the hypothesis bounds the sum by , which is negligible since is a polynomial (closure of the negligible class under polynomial multiplication). Hence . □
Uniformity in is essential, and no argument derives it from the weaker hypothesis that each is negligible for every fixed : there the threshold beyond which the -th term is small can depend on , and the dependence cannot be removed. A countermodel makes this concrete: take and let be the point mass at if and the point mass at otherwise. For every fixed the advantage is nonzero only at , hence negligible; yet and are the point masses at and , perfectly distinguishable.
Applications usually obtain the conclusion by a stronger, structural route. Suppose the chain arises from a single underlying assumption : neighbouring hybrids and differ only in that one designated component is drawn from in the former and from in the latter, and each hybrid is efficiently samplable given and a sample of that component. Then the random-index distinguisher for the pair , on challenge , samples uniformly from , builds the hybrid with in the designated position, and runs ; writing , its distinguishing advantage equals . Since is a single PPT machine, the assumption makes its advantage negligible, and . Note that this argument bounds ’s total advantage directly, bypassing the lemma’s uniform per-step hypothesis rather than discharging it; the lemma itself covers the general case in which no such common structure is available.
The hybrid argument is precisely where the “polynomially many” constraint earns its keep. A negligible per-step advantage multiplied by a polynomial number of steps remains negligible; a negligible per-step advantage multiplied by, say, steps need not. This is why constructions that would require exponentially many hybrids do not yield security proofs, and why the closure of negligibility under polynomial factors is not a technicality but the load-bearing wall of the whole edifice.
We can now state what it means to “break” a scheme. The modern idiom expresses every security definition as a game (or experiment) played between a challenger and an adversary . The challenger, following a fixed protocol, sets up the scheme, answers whatever queries the adversary may pose, and at the end declares the adversary a winner or loser by outputting a single bit. Security says that no PPT adversary wins by more than it could by trivial guessing.
A security game (or experiment) is a PPT interactive algorithm, the challenger, that takes , interacts with an adversary , and finally outputs a bit , where denotes “adversary wins”. The advantage of is a measure of how much better than trivial its winning probability is; its precise form depends on the type of game:
Distinguishing (indistinguishability) games, where the challenger secretly chooses a uniform bit and outputs a guess ; the adversary wins iff . Here
Trivial guessing achieves winning probability , hence advantage .
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) , and one simply sets
A scheme is secure with respect to the game if for every PPT adversary ,
Two remarks on the shape of this definition are in order. First, the quantifier order is essential: for every PPT adversary, the advantage is negligible. For each fixed adversary there may be a different negligible bound; the claim is universal over the entire class. Second, the use of on the right is what makes the definition asymptotic and clean: it is robust to the polynomial slop that reductions introduce, and it captures “the adversary does no better than the trivial strategy, up to an amount that vanishes faster than any inverse polynomial”.
To anchor the abstraction with machinery already on the table, consider the distinguishing game for a pseudorandom generator —the primitive that witnessed strictness in Proposition 1.10:
The challenger samples uniformly. If it samples a seed and sends ; if it sends a uniform .
The adversary outputs a guess ; the game outputs iff .
The generator is secure iff is negligible for every PPT . Here the game packaging and the ensemble packaging coincide: the two situations are the fixed ensembles and , and the displayed identity in Definition 1.15 shows the game advantage of is exactly half its distinguishing advantage in the sense of Definition 1.9—so the game is secure iff the ensembles are computationally indistinguishable. The game form earns its keep beyond this case: when the adversary chooses part of the challenge or queries oracles adaptively, the interaction no longer collapses to a comparison of two fixed ensembles, and the game is the more general packaging—the shape the security definitions of the later sections take.
Once we phrase security as a game, proofs become sequences of games. One starts from the real security game and rewrites it through a series of games , each differing from the last by a small, justifiable change, until reaching a final game in which the adversary provably has zero (or trivially negligible) advantage. Each hop is justified by exactly one of three moves: the two games are identical unless some negligible-probability “bad” event occurs, so their winning probabilities differ by at most (on the complement of that event the two runs coincide); or distinguishing the two games would break a hardness assumption (a reduction, below); or the change is purely syntactic. Bounding the total advantage is then a telescoping sum across hops—a structured cousin of the hybrid argument (Lemma 1.13). This discipline keeps otherwise sprawling proofs honest and auditable.
The engine of provable security is the reduction. 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 is secure” by establishing the contrapositive “ is broken is solved”.
A computational problem consists of a PPT instance generator 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 is
The problem is hard if for every PPT (for a search problem), or if every PPT decides the instance with at most negligible advantage, in the sense of Definition 1.15 (for a decision problem).
Let be a scheme with security game and a computational problem. A (black-box) reduction from breaking to solving is a PPT oracle algorithm with the following per-adversary guarantee: for every adversary , writing for its advantage, the algorithm —which runs as a subroutine, simulating ’s game internally—solves with success probability
where is a function fixed by the reduction (not by ) that maps every non-negligible to a non-negligible bound. The running time of is measured with each call to counted as one step, so “PPT” bounds ’s own work, and hence its number of calls to , by a polynomial in ; the running time of is then polynomial whenever ’s is, however many times runs . How far degrades is the reduction’s loss, discussed below. The reduction is black-box because uses only through its input/output interface, making no use of ’s code.
The structure of a reduction is always the same and is worth stating as a recipe. To prove “if is hard then is secure”:
Assume toward the contrapositive a PPT adversary that breaks with non-negligible advantage .
Construct a PPT algorithm that, given a random instance of , embeds that instance into a simulated security game for . The simulation must be faithful: the view presents to must follow (perfectly, statistically, or computationally) the distribution of the real game, so that ’s advantage carries over.
Run . From whatever does to win its game, extracts a solution to the -instance.
Conclude that solves with non-negligible probability, contradicting the hardness of . Therefore no such exists, and is secure.
A complete, genuine reduction illustrates the point.
Let be the computational Diffie–Hellman problem in a cyclic group of prime order , the setting of the Math Guide (§“The discrete logarithm problem”): given for uniform , compute . Consider the “key-recovery” game for a key-exchange scheme in which the adversary, given the public transcript , wins iff it outputs the shared key . If is hard, then no PPT adversary wins with noticeable probability.
Suppose is a PPT adversary that, on input a transcript , outputs with probability . Construct solving . On input a instance :
The reduction forms the simulated transcript and feeds it to as the public transcript of .
Because are uniform in the instance and in the real game, the view of follows identically the distribution of its view in (the simulation is perfect; no loss in faithfulness).
When outputs a candidate key , outputs as its answer.
Since the simulated and real views are identically distributed, outputs with exactly probability ; whenever it does, returns the correct solution. Hence
The running time of is that of plus a constant amount of group bookkeeping, hence polynomial. If were noticeable, would solve with noticeable probability, contradicting its hardness. Therefore is not noticeable, as claimed. In fact, since is PPT and is hard (Definition 1.19, search branch), . □
This example is deliberately tight: the reduction loses nothing, calls the adversary once, and converts advantage into success probability exactly . Most reductions are not so fortunate, which leads to the quantitative anatomy of a reduction.
Consider a reduction that transforms an adversary running in time with advantage into a -solver running in time with success probability . The security loss is the factor
the ratio of the solver’s work-per-success to the adversary’s work-per-success. A reduction is tight if (a small constant, ideally ), and loose if grows with (e.g. , the number of random-oracle queries (Definition 1.26 below), or , the number of signature queries, or ). Two common sources of loss are: an advantage gap (the solver succeeds far less often than the adversary, e.g. because the reduction must guess where to embed its instance among queries, succeeding only with probability ); and a time blow-up (the reduction runs the adversary many times, as in rewinding/forking arguments).
Asymptotically, loss is invisible: a polynomial loss factor turns a negligible advantage into a negligible advantage and a hard problem into security, without qualification. Concretely, however, loss carries a cost. Suppose a scheme reduces to a problem believed to offer bits of security, but the reduction loses a factor (not unusual: random-oracle queries times a forking-lemma square-root loss can be much worse). Then the proof guarantees only bits of security for the scheme. To restore a -bit guarantee one must enlarge the group so that the underlying problem offers bits—larger keys, slower operations. A tight reduction lets the scheme inherit the full strength of the assumption at the smallest parameters; a loose one imposes a permanent cost on every user. This is why tightness is a first-class design goal in modern cryptography, not a theoretical nicety.
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 afterward 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 random-oracle queries whose answers are drawn from a set of size , the forked run succeeds with probability at least , i.e. on the order of . The square in is a quadratic security loss: to keep noticeable one needs noticeably large, roughly halving the bit-security extracted. Such arguments—central to the analyses of Schnorr-type and Fiat–Shamir signatures that this volume builds toward—are the archetype of loose but still valid reductions.
Reductions reduce security to assumptions. Which assumptions one is willing to make defines the model in which a proof 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 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—crucially—to the reduction. No party holds the “code” of ; it can only be queried.
The random oracle model is an idealisation: real hash functions are fixed, public algorithms, not truly random functions. The motivation for adopting it is that the reduction gains 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, and this yields two additional capabilities. Observability: the reduction sees every query the adversary makes to . 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 where is part of a CDH challenge—so that the adversary’s success necessarily reveals the solution. Neither capability exists for a concrete standard-model hash function, which fixes its outputs in advance and hides its internal queries.
In the “full domain hash” signature, the signer signs a message as , where is an RSA private key—a modulus with secret prime factors and a secret exponent paired with a public so that for coprime to , by Euler’s theorem (Math Guide, §“Fermat’s little theorem and Euler’s theorem”); thus is a permutation of the unit group that only the holder of can invert—and is a hash function mapping messages into . (Restricting to units costs nothing: a nonzero non-unit of shares a factor with , so stumbling on one factors . Hash functions appear here informally, as this sketch needs them; their formal syntax and security games are the business of the next-but-one section.) To prove unforgeability one reduces to RSA inversion: given a challenge (find ), the reduction programs the oracle so that for a random subset of messages (embedding the challenge) and for the rest (where it knows the “signature” ); with each drawn uniformly from , the programmed values are distributed exactly as honest oracle answers on ’s range. When the forger outputs a forgery on a message where the reduction embedded the challenge, the reduction extracts . This proof has no known standard-model analogue for the plain scheme: it relies essentially on programming . The cost is a security loss (the reduction must guess which message the forger attacks, incurring a factor unless cleverly optimised)— connecting back to Definition 1.22.
A proof in the ROM is a proof about an idealised world: deploying the scheme instantiates 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 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 suffer this fate, and the working stance of this volume is the practical one: a ROM proof is strong positive evidence, not a guarantee, and a standard-model proof is preferred when one is available at comparable cost. One caveat looks forward. 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.
Between and beyond these poles lie further idealisations 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 natural 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, and the constructions ahead invoke them by name where they require them.
The asymptotic language—“negligible”, “polynomial”, “for all sufficiently large ”—is mathematically clean but operationally silent. It establishes that a scheme is eventually secure; it does not establish whether this deployment with these parameters resists an adversary with that budget. Concrete (or exact) security supplies the missing numbers.
Fix the security parameter to a concrete value (so all sizes are fixed). A scheme is -secure for a game if every adversary running in time at most has advantage . More refined statements bound the advantage as an explicit function of the adversary’s resources, e.g. time , number of queries , and memory : .
A scheme (or problem) is commonly said to offer bits of security when the cheapest known attack achieving constant success probability (say at least ) costs on the order of elementary operations. A proof may justify the stronger, explicit claim that every adversary running in time has advantage at most about , but that linear advantage bound is not implied merely by the absence of a faster known attack. Thus “-bit security” is a concrete estimate, relative to a specified attack model and state of knowledge, that breaking the scheme costs roughly work.
The relationship to the asymptotic picture is the following: one chooses the security parameter precisely so that the resulting concrete scheme delivers the desired number of bits of security. In the cleanest case the two coincide, , but in general one must account for the actual cost of the best attack on the underlying problem.
For a generic-group or hash-based primitive, doubling the output length doubles the bit security: a hash with -bit output offers -bit collision resistance—by the birthday bound (Math Guide, §“The union bound and a birthday calculation”)—and -bit preimage resistance, so the parameter and the security level track simply. For discrete-logarithm-based primitives the accounting differs and instructs. In a group of prime order , generic attacks (baby-step/giant-step, Pollard’s rho) solve discrete logarithm in time (Math Guide, §“The discrete logarithm problem”). Hence a prime-order elliptic-curve group whose order is bits offers only about bits of security—one halves the bit length of the group order to obtain the generic security level. For discrete logarithm in a finite-field multiplicative group, sub-exponential index-calculus attacks additionally force the ambient field modulus into the thousands of bits for -bit security. This is precisely why elliptic-curve groups, for which no comparable sub-exponential classical attack is known, are preferred: they deliver -bit security at rather than thousands of bits. The single number conceals a problem-specific translation from all parameter sizes to the security level. The working groups of this volume are priced by exactly this arithmetic: the Pasta curves assembled in the Math Guide (§“Pallas and Vesta assembled”) have prime order close to , so the square-root rule prices generic discrete logarithm there at about operations; the next section audits them criterion by criterion under “Instantiation on elliptic curves; the Pasta curves”.
Combining the preceding components yields the practitioner’s parameter-selection recipe. Decide the target security level (commonly ). Identify the underlying hard problem and the cost of its best attack as a function of the parameter (e.g. for elliptic-curve discrete log), and set the parameter so the problem itself offers bits (here ). Then subtract the reduction’s security loss (Definition 1.22): if the proof loses a factor (that is, bits), the problem must offer bits for the scheme to offer , so one enlarges the parameter accordingly—or, with a tight reduction, one need not. Finally, sanity-check against the ROM caveat (Remark 1.29): a ROM proof bounds only black-box attacks on the hash, so the concrete hash must additionally exhibit no exploitable structure. The clean asymptotic theorem “the scheme is secure if the problem is hard” thus unfolds, through the quantitative machinery of this section, into a concrete choice of bytes.
A caution that frames everything above is in order. 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 value of the framework is not that it renders schemes unconditionally safe—nothing can—but that it renders the conditions of safety explicit, falsifiable, and modular, so that progress on assumptions and attacks translates directly into recalibrated, auditable guarantees. Everything this monograph builds rests on this discipline.