This volume of The Zcash Arboretum constructs the cryptographic primitives from which a shielded protocol is built: each is defined, constructed, and proved secure against an explicitly defined adversary. It assumes the Math Guide, whose groups, finite fields, elliptic curves, probability, and model of computation are used throughout without re-derivation.
Every guarantee in the volume is a claim about an adversary, and every security definition is a game: a challenger, an efficient adversary, and an advantage that must be negligible. A proof is a reduction that converts any adversary with non-negligible advantage into a solver for a long-studied computational problem, with the loss of the reduction accounted for down to a concrete bit-security budget. Within this framework the volume treats, in turn, the following adversaries: one who recovers the exponent behind a public group element, and with it every key; one who finds two documents with a common digest, or reuses a digest outside its intended role; a receiver who learns a committed value before the commitment is opened, and a committer who opens a commitment to a value other than the one committed; one who, given oracle access, distinguishes a function keyed by a short secret from a uniformly random function; one who controls a channel and reads, splices, or forges the messages that pass over it; one who interposes between two parties and terminates both ends of a conversation that each party believes secure; one who produces a signature that the signer never made; a cheating prover who convinces a verifier of a false statement, and a curious verifier who extracts from a transcript information about the witness it hides; and one who proves membership of an element in a set that does not contain it. The primitives that meet these definitions—hash functions, commitments, pseudorandom functions, authenticated encryption, key agreement, signatures, zero-knowledge arguments, and Merkle trees—are the primitives on which the deployed protocol relies.