The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

1 The provable-security model

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 𝖯≠𝖭𝖯—that problems whose solutions can be checked in polynomial time are not all solvable in polynomial time—and considerably more. Security is instead reduced to the conjectured hardness of computational problems that have resisted decades of attack, such as factoring, discrete logarithm and decisional Diffie–Hellman: any adversary that breaks the scheme can be transformed mechanically into an algorithm that solves the underlying problem.

1.1 Adversaries and the security parameter

The vocabulary of efficiency is that of the closing section of the Math Guide, recalled here with the refinements cryptography needs.

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 1λ, 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 λ.

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 ⌈log2λ⌉-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.

Remark 1.1.

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 𝒜 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, 𝒜 halts within p(|x|) steps: the strict, worst-case notion of the Math Guide (§“Algorithms, running time, and PPT”). We write y←𝒜(x) for the random variable obtained by running 𝒜 on x with freshly sampled randomness, and y:=𝒜(x;r) for the deterministic output when the random tape is fixed to the string r. The honest algorithms and the adversary alike are modelled as PPT machines.

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”).

Definition 1.2 (Non-uniform PPT).

A non-uniform PPT adversary is a family {𝒜λ}λ∈ℕ 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 𝒜λ. The advice may depend arbitrarily on λ but not on the particular inputs drawn at run time.

Remark 1.3.

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.

Remark 1.4 (Expected versus strict polynomial time, and quantum adversaries).

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.

1.2 Distribution ensembles and indistinguishability

The most basic security goal is that no adversary distinguishes two situations: a real protocol transcript from a simulated one, an encryption of m0 from an encryption of m1, a pseudorandom string from a truly random one. The situations are formalised as ensembles of probability distributions.

Definition 1.5 (Probability ensemble).

A probability ensemble is a sequence X={Xλ}λ∈ℕ of probability distributions (equivalently, random variables), one for each value of the security parameter, where Xλ is supported on binary strings whose length is bounded by a polynomial in λ. There is often an additional index—an input a—written {Xλ(a)}; for clarity we suppress it unless needed.

The statistical distance of the Math Guide (§“Statistical distance”) is recalled for countable supports, which ensembles require; the Math Guide treats finite ones.

Definition 1.6 (Statistical distance).

Let X,Y be discrete random variables over a common finite or countable set S. Their statistical distance (or total variation distance) is

Δ⁢(X,Y):=12⁢∑s∈S|Pr⁡[X=s]−Pr⁡[Y=s]|.
Proposition 1.7 (Variational characterisation).

For X,Y over S,

Δ⁢(X,Y)=maxT⊆S⁡(Pr⁡[X∈T]−Pr⁡[Y∈T])=maxD⁡(Pr⁡[D⁢(X)=1]−Pr⁡[D⁢(Y)=1]),

where the last maximum ranges over all (even computationally unbounded, deterministic) decision functions D:S→{0,1}. In particular, no procedure whatsoever— efficient or not—can distinguish X from Y with advantage exceeding Δ(X,Y).

Proof.

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 T=D−1(1), so the maximum over D equals the maximum over T; a randomised D is a convex combination of deterministic ones and cannot do better. □

Proposition 1.8 (Properties of statistical distance).

The statistical distance is a metric on probability distributions: 0≤Δ(X,Y)≤1, it is symmetric, Δ(X,Y)=0 iff X and Y are identically distributed, and it satisfies the triangle inequality Δ(X,Z)≤Δ(X,Y)+Δ(Y,Z). Moreover it never increases under (possibly randomised) post-processing: for any function—more generally, any randomised algorithm—f,

Δ⁢(f⁢(X),f⁢(Y))≤Δ⁢(X,Y).
Proof.

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 f:ℕ→ℝ≥0 is negligible, written f=negl(λ), if for every c∈ℕ there exists λ0 such that f(λ)<λ−c for all λ≥λ0. A function is non-negligible if it is not negligible; it is noticeable if there exists c with f(λ)≥λ−c for all sufficiently large λ (noticeable functions are non-negligible, but not conversely); it is overwhelming if 1−f 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.

Definition 1.9 (Perfect, statistical, and computational indistinguishability).

Let X={Xλ} and Y={Yλ} be probability ensembles.

  • •

    The ensembles X and Y are perfectly indistinguishable, written X≡Y, if Xλ and Yλ are identically distributed for every λ; equivalently Δ(Xλ,Yλ)=0 for all λ.

  • •

    The ensembles X and Y are statistically indistinguishable, written X≈sY, if their statistical distance is negligible:

    Δ⁢(Xλ,Yλ)=negl⁡(λ).
  • •

    The ensembles X and Y are computationally indistinguishable, written X≈cY, if for every PPT algorithm D (the distinguisher), the function

    AdvX,Ydist⁢(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 Un for the uniform distribution on {0,1}n. A one-way function is a polynomial-time computable h:{0,1}∗→{0,1}∗ that no PPT algorithm inverts on a random input: for every PPT 𝒜,

Pr⁡[h⁢(𝒜⁢(1λ,h⁢(x)))=h⁢(x)]=negl⁡(λ)(x←Uλ).

A pseudorandom generator (PRG) is a polynomial-time computable G:{0,1}λ→{0,1}2⁢λ whose output on a uniform seed is computationally indistinguishable from uniform, {G(Uλ)}≈c{U2⁢λ}; the doubling stretch is a normalisation. Whether one-way functions exist is open, which is why the second strictness below is stated conditionally.

Proposition 1.10 (Hierarchy).

For all ensembles X,Y:

X≡Y⟹X≈sY⟹X≈cY.

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.

Proof.

If X≡Y then Δ(Xλ,Yλ)=0, which is negligible, so X≈sY. If X≈sY, then for any—in particular any PPT—distinguisher D, Proposition 1.7 gives AdvX,Ydist(D,λ)≤Δ(Xλ,Yλ)=negl(λ), so X≈cY.

For strictness of the first implication, let Xλ be uniform on {0,1}λ and let Yλ be uniform on {0,1}λ∖{0λ}. They are not identically distributed (the point 0λ has probabilities 2−λ and 0), so not perfectly indistinguishable, yet Δ(Xλ,Yλ)=2−λ=negl(λ), 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 G be a PRG, let Xλ:=G(Uλ), and let Yλ:=U2⁢λ. By definition of a PRG, X≈cY. But Xλ is supported on at most 2λ strings out of 22⁢λ, so a set T equal to the image of G has Pr[Xλ∈T]=1 while Pr[Yλ∈T]≤2λ/22⁢λ=2−λ; hence Δ(Xλ,Yλ)≥1−2−λ, which is not negligible. Thus X≈cY but X≉sY. □

Remark 1.11 (Cost and benefit of computational indistinguishability).

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.

1.3 The hybrid argument

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.

Lemma 1.12 (Closure under efficient post-processing).

If X≈cY and M is any PPT algorithm, then the ensembles {M(1λ,Xλ)} and {M(1λ,Yλ)} satisfy {M(Xλ)}≈c{M(Yλ)}.

Proof.

Suppose some PPT distinguisher D separates {M(Xλ)} from {M(Yλ)} with advantage δ(λ). Define D′:=D∘M, i.e. D′(1λ,z):=D(1λ,M(1λ,z)). Since M and D are both PPT, so is D′. Then

AdvX,Ydist⁢(D′,λ)=|Pr⁡[D⁢(M⁢(Xλ))=1]−Pr⁡[D⁢(M⁢(Yλ))=1]|=δ⁢(λ).

By X≈cY the left side is negligible, so δ is negligible. □

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.

Lemma 1.13 (Hybrid lemma).

Let t=t(λ) be polynomially bounded, and let Hλ0,Hλ1,…,Hλt be a sequence of distributions (the hybrids). Suppose that for every PPT distinguisher D the neighbouring advantages

αi⁢(D,λ):=|Pr⁡[D⁢(Hλi)=1]−Pr⁡[D⁢(Hλi+1)=1]|

are uniformly negligible: a single negligible function ν (depending on D) satisfies αi(D,λ)≤ν(λ) for all i∈{0,…,t(λ)−1} simultaneously. Equivalently, max0≤i<t⁢(λ)αi(D,λ)=negl(λ), i.e. αi⁢(λ)(D,λ) is negligible along every index function i(λ)—arbitrary, not merely efficiently computable, since the maximising index need not be efficient. Then {Hλ0} and {Hλt} are computationally indistinguishable, i.e. for every PPT D, |Pr[D(Hλ0)=1]−Pr[D(Hλt)=1]|=negl(λ).

Proof.

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=0t−1(Pr⁡[D⁢(Hλi)=1]−Pr⁡[D⁢(Hλi+1)=1])|≤∑i=0t−1αi⁢(D,λ),

and the hypothesis bounds the sum by t(λ)⋅ν(λ), which is negligible since t is a polynomial (closure of the negligible class under polynomial multiplication). Hence {H0}≈c{Ht}. □

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 t(λ)=λ+1 and let Hλi be the point mass at 0 if i≤λ and the point mass at 1 otherwise. For every fixed i the advantage αi(D,λ) is nonzero only at λ=i, hence negligible; yet Hλ0 and Hλt⁢(λ) are the point masses at 0 and 1, perfectly distinguishable.

Applications usually obtain the conclusion by a stronger, structural route. Suppose the chain arises from a single underlying assumption X≈cY: neighbouring hybrids Hλi and Hλi+1 differ only in that one designated component is drawn from Xλ in the former and from Yλ in the latter, and each hybrid is efficiently samplable given (1λ,i) and a sample of that component. Then the random-index distinguisher D′ for the pair (X,Y), on challenge z, samples i uniformly from {0,…,t−1}, builds the hybrid with z in the designated position, and runs D; writing pi:=Pr[D(Hλi)=1], its distinguishing advantage equals |1t∑i=0t−1(pi−pi+1)|=|p0−pt|/t. Since D′ is a single PPT machine, the assumption makes its advantage negligible, and |p0−pt|≤t(λ)⋅Adv(D′)=negl(λ). This argument bounds the total advantage of D 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.

Remark 1.14.

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.

1.4 Security as a game

The standard formulation expresses a security definition as a game (or experiment) between a challenger and an adversary 𝒜: 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.

Definition 1.15 (Security game and advantage).

A security game (or experiment) 𝖦 is a PPT interactive algorithm, the challenger, that takes 1λ, interacts with an adversary 𝒜, and finally outputs a bit 𝖦𝒜(λ)∈{0,1}, where 1 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 b∈{0,1} and 𝒜 outputs a guess b′; the adversary wins iff b′=b. Here

    Adv𝖦⁢(𝒜,λ):=|Pr⁡[𝖦𝒜⁢(λ)=1]−12|=12⁢|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𝖦⁢(𝒜,λ):=Pr⁡[𝖦𝒜⁢(λ)=1].

Figure 1 draws the interaction.

Refer to caption
Figure 1: The security game of Definition 1.15, with no scheme instantiated. The challenger (blue) runs the setup on 1λ, sampling the secret bit b in a distinguishing game, and passes the public part of the setup to the adversary (black). It answers the adversary’s queries (grey bands), before and after it sends, in a distinguishing game, a message prepared with b, and it receives the final output: a guess b′ in a distinguishing game; a forgery, preimage or discrete logarithm in a search game. The win predicate turns the run into the output bit 𝖦𝒜(λ), and the advantage is read off its distribution. The pseudorandomness game of Example 1.17, the PRF game of Definition 5.4, the CPA game of Definition 6.4 and the unforgeability game of Definition 8.2 are instances.
Definition 1.16 (Security relative to a game).

A scheme is secure with respect to the game 𝖦 if for every PPT adversary 𝒜,

Adv𝖦⁢(𝒜,λ)=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.

Example 1.17 (Pseudorandomness, as a game).

The distinguishing game for a pseudorandom generator G:{0,1}λ→{0,1}2⁢λ, the primitive that witnessed strictness in Proposition 1.10, is the following.

  1. 1.

    The challenger samples b←{0,1} uniformly. If b=0 it samples a seed s←{0,1}λ and sends z:=G(s); if b=1 it sends a uniform z←{0,1}2⁢λ.

  2. 2.

    The adversary 𝒜 outputs a guess b′; the game outputs 1 iff b′=b.

The generator is secure iff Adv(𝒜,λ)=|Pr[b′=b]−12| is negligible for every PPT 𝒜. In this case the game and ensemble formulations coincide: the two situations are the fixed ensembles {G(Uλ)} and {U2⁢λ}, 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. When the adversary chooses part of the challenge or queries oracles adaptively, the interaction no longer reduces to a comparison of two fixed ensembles and the game form is required; the security definitions of the later sections are games.

Remark 1.18 (Game-hopping).

Game-based proofs are sequences of games: one rewrites the real security game through a series of games 𝖦0,𝖦1,…,𝖦k, 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 Pr[bad] (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 variant of the hybrid argument (Lemma 1.13) that makes a long proof auditable one hop at a time.

1.5 Reductions

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”.

Definition 1.19 (Computational problem and hardness).

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 ℬ is

SuccΠ⁢(ℬ,λ):=Pr⁡[ℬ⁢(1λ,Inst⁢(1λ))⁢ solves the instance].

The problem Π is hard if SuccΠ(ℬ,λ)=negl(λ) for every PPT ℬ (for a search problem), or if every PPT ℬ decides the instance with at most negligible advantage, Adv(ℬ,λ)=negl(λ) in the sense of Definition 1.15 (for a decision problem).

Definition 1.20 (Black-box reduction).

Let X be a scheme with security game 𝖦X and Π a computational problem. A (black-box) reduction from breaking X to solving Π is a PPT oracle algorithm ℛ with the following per-adversary guarantee: for every adversary 𝒜, writing εX(λ):=Adv𝖦X(𝒜,λ) for its advantage, the algorithm ℛ𝒜—which runs 𝒜 as a subroutine, simulating 𝒜’s game internally—solves Π with success probability

SuccΠ⁢(ℛ𝒜,λ)≥f⁢(εX⁢(λ),λ),

where f is a function fixed by the reduction (not by 𝒜) that maps every non-negligible εX 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 f degrades εX 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.

Every reduction has the same structure. To prove “if Π is hard then X is secure”:

  1. 1.

    Assume, towards the contrapositive, a PPT adversary 𝒜 that breaks X with non-negligible advantage εX.

  2. 2.

    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.

  3. 3.

    Run 𝒜. From whatever 𝒜 does to win its game, ℛ extracts a solution to the Π-instance.

  4. 4.

    Conclude that ℛ solves Π with non-negligible probability, contradicting the hardness of Π. Therefore no such 𝒜 exists, and X is secure.

Figure 2 draws this structure.

Refer to caption
Figure 2: A black-box reduction, Definition 1.20, in the four-step structure of §1.5. The reduction ℛ (outer frame) receives a random instance of Π and embeds it in a simulated security game 𝖦X (blue, dashed), whose challenger it plays. The adversary 𝒜 (black) is opaque: the reduction reaches it only through its input/output interface. The dashed boundary is all that 𝒜 sees; the simulation makes it faithful to the real game, so that the advantage εX of 𝒜 carries over. From the output of 𝒜, the reduction extracts a solution to the instance, with success probability at least f(εX,λ).
Theorem 1.21 (Hard-core security of the Diffie–Hellman-style key, schematically).

Let Π=CDH be the computational Diffie–Hellman problem in a cyclic group 𝔾=⟨g⟩ of prime order q, the setting of the Math Guide (§“The discrete logarithm problem”): given (g,ga,gb) for uniform a,b∈ℤ/qℤ, compute ga⁢b. Consider the “key-recovery” game 𝖦X for a key-exchange scheme in which the adversary, given the public transcript (ga,gb), wins iff it outputs the shared key ga⁢b. If CDH is hard, then no PPT adversary wins 𝖦X with noticeable probability.

Proof.

Suppose 𝒜 is a PPT adversary that, on input a transcript (ga,gb), outputs ga⁢b with probability εX(λ)=Adv𝖦X(𝒜,λ). Construct ℛ solving CDH. On input a CDH instance (g,A,B)=(g,ga,gb):

  1. 1.

    The reduction ℛ forms the simulated transcript (A,B) and feeds it to 𝒜 as the public transcript of 𝖦X.

  2. 2.

    Because (a,b) are uniform in the CDH instance and in the real game, the view of 𝒜 follows identically the distribution of its view in 𝖦X (the simulation is perfect; no loss in faithfulness).

  3. 3.

    When 𝒜 outputs a candidate key K, ℛ outputs K as its CDH answer.

Since the simulated and real views are identically distributed, 𝒜 outputs K=ga⁢b with exactly probability εX(λ); whenever it does, ℛ returns the correct CDH solution. Hence

SuccCDH⁢(ℛ,λ)=εX⁢(λ).

The running time of ℛ is that of 𝒜 plus a constant amount of group bookkeeping, hence polynomial. If εX were noticeable, ℛ would solve CDH with noticeable probability, contradicting its hardness. Therefore εX(λ) is not noticeable, as claimed. Moreover, since ℛ is PPT and CDH is hard (Definition 1.19, search branch), εX(λ)=SuccCDH(ℛ,λ)=negl(λ). □

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.

Definition 1.22 (Reduction loss and tightness).

Consider a reduction ℛ that transforms an adversary running in time t with advantage ε into a Π-solver running in time t′=t+tℛ with success probability ε′. The security loss is the factor

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 L(λ)=O(1) (a small constant, ideally 1), and loose if L(λ) grows with λ (e.g. L=qH, the number of random-oracle queries (Definition 1.26 below), or L=qs, the number of signature queries, or L=λ). 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 q queries, succeeding only with probability 1/q); and a time blow-up t′≫t (the reduction runs the adversary many times, as in rewinding/forking arguments).

Remark 1.23 (Why loss matters concretely).

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 L=240 (not unusual: qH≈260 random-oracle queries times a forking-lemma square-root loss can be much worse). Then the proof guarantees only 128−40=88 bits of security for the scheme. To restore a 128-bit guarantee one must enlarge the group so that the underlying problem offers 168 bits—larger keys, slower operations. A tight reduction lets the scheme inherit the full strength of the assumption at the smallest parameters, and a loose one forces larger ones. Tightness is therefore a design goal.

Remark 1.24 (Rewinding and the forking lemma, in brief).

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 ε(ε/q−1/h), i.e. on the order of ε2/q. The square in ε is a quadratic security loss: to keep ε2/q noticeable one needs ε noticeably large, roughly halving the bit-security extracted. Such arguments, which later sections of this volume use for Schnorr-type and Fiat–Shamir signatures, are the archetype of loose but valid reductions.

1.6 The standard model and the random oracle model

The assumptions a proof makes define the model in which it resides. Two models predominate.

Definition 1.25 (Standard model).

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.

Definition 1.26 (Random oracle model).

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, in particular, to the reduction. No party holds the “code” of 𝒪; 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.

Remark 1.27 (The powers of the random oracle: observability and programmability).

In the ROM the reduction simulates the oracle for the adversary. 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 𝒪(x):=B where B 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.

Example 1.28 (The benefit of the ROM: full-domain hash, sketched).

In the “full domain hash” signature, the signer signs a message m as σ=H(m)dmodN, where (N,d) is an RSA private key—a modulus N=pq with secret prime factors and a secret exponent d paired with a public e so that xe⁢d≡x(modN) for x coprime to N, by Euler’s theorem (Math Guide, §“Fermat’s little theorem and Euler’s theorem”); thus x↦xe is a permutation of the unit group (ℤ/N⁢ℤ)× that only the holder of d can invert—and H is a hash function mapping messages into (ℤ/N⁢ℤ)×. (Restricting to units costs nothing: a nonzero non-unit of ℤ/Nℤ shares a factor with N, so finding one factors N. Hash functions appear here informally, as this sketch needs them; their formal syntax and security games are given in the section after next.) To prove unforgeability one reduces to RSA inversion: given a challenge y (find yd), the reduction programs the oracle so that for a random subset of messages H(m):=y⋅rme (embedding the challenge) and for the rest H(m):=rme (where it knows the “signature” rm); with each rm drawn uniformly from (ℤ/N⁢ℤ)×, the programmed values are distributed exactly as honest oracle answers on H’s range. When the forger outputs a forgery on a message where the reduction embedded the challenge, the reduction extracts yd. This proof has no known standard-model analogue for the plain scheme: it relies essentially on programming H. The cost is a security loss (the reduction must guess which message the forger attacks, incurring a factor qH unless the reduction is optimised)—a loss in the sense of Definition 1.22.

Remark 1.29 (The status of the ROM: heuristic, not theorem).

A proof in the ROM is a proof about an idealised model: 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 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.

Remark 1.30 (Relatives: CRS, generic-group, and algebraic-group models).

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.

1.7 Concrete security and the bit-security budget

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.

Definition 1.31 (Concrete security: (t,ε)-security).

Fix the security parameter to a concrete value (so all sizes are fixed). A scheme is (t,ε)-secure for a game 𝖦 if every adversary running in time at most t has advantage Adv𝖦(𝒜)≤ε. More refined statements bound the advantage as an explicit function of the adversary’s resources, e.g. time t, number of queries q, and memory s: Adv𝖦(𝒜)≤f(t,q,s).

Definition 1.32 (n-bit security).

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 12) costs on the order of 2n elementary operations. A proof may justify the stronger, explicit claim that every adversary running in time t has advantage at most about t/2n, 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 2128 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, n=λ; in general the choice accounts for the actual cost of the best attack on the underlying problem.

Example 1.33 (Why λ≠n for discrete logarithm).

For a generic-group or hash-based primitive, doubling the output length doubles the bit security: a hash with 2n-bit output offers n-bit collision resistance—by the birthday bound (Math Guide, §“The union bound and a birthday calculation”)—and 2n-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 q≈2ℓ, generic attacks (baby-step/giant-step, Pollard’s rho) solve discrete logarithm in time ≈q=2ℓ/2 (Math Guide, §“The discrete logarithm problem”). Hence a prime-order elliptic-curve group whose order is 256 bits offers only about 128 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 128-bit security. Elliptic-curve groups, for which no comparable sub-exponential classical attack is known, are preferred for this reason: they deliver n-bit security at ℓ≈2n rather than thousands of bits. The single number n thus conceals a problem-specific translation from parameter sizes to the security level. The same arithmetic assesses the working groups of this volume: the Pasta curves assembled in the Math Guide (§“Pallas and Vesta assembled”) have prime order close to 2254, so the square-root rule puts the cost of generic discrete logarithm there at about 2127 operations; the next section audits them criterion by criterion under “Instantiation on elliptic curves; the Pasta curves”.

Remark 1.34 (Reading a bit-security budget end to end).

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ℓ/2 for elliptic-curve discrete log), and the parameter is set so the problem itself offers n bits (here ℓ=2n=256). Third, the reduction’s security loss is subtracted (Definition 1.22): if the proof loses a factor L=2k (that is, k bits), the problem must offer n+k bits for the scheme to offer n, so one enlarges the parameter accordingly—or, with a tight reduction, one need not. Finally, the choice is checked 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 asymptotic theorem “the scheme is secure if the problem is hard” thus becomes a concrete choice of parameter sizes.

Remark 1.35 (Scope of a security proof).

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.