Crypto Guide
Abstract
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.
Contents
- 1 The provable-security model
-
2 Hardness assumptions
- 2.1 The discrete logarithm problem
- 2.2 Diffie–Hellman: computational and decisional
- 2.3 The assumption hierarchy
- 2.4 Generic algorithms and the square-root barrier
- 2.5 Pohlig–Hellman and the necessity of large prime order
- 2.6 Instantiation on elliptic curves; the Pasta curves
- 2.7 Quantum adversaries: Shor’s algorithm
- 2.8 Standing assumptions
-
3 Hash functions and the random oracle model
- 3.1 Syntax
- 3.2 Security notions: preimage, second-preimage, and collision resistance
- 3.3 The birthday bound on generic collision finding
- 3.4 The random oracle model
- 3.5 Domain separation and personalisation
- 3.6 Hashing to a field element
- 3.7 Hashing to a curve point
- 3.8 Arithmetisation-friendly hashing: Poseidon
- 3.9 The transparent layer’s hashes
-
4 Commitment schemes
- 4.1 Commit and reveal
- 4.2 Syntax
- 4.3 Hiding and binding
- 4.4 Incompatibility of perfect hiding and perfect binding
- 4.5 Hash-based commitments
- 4.6 The Pedersen commitment
- 4.7 Pedersen vector commitments
- 4.8 Sinsemilla: an algebraic hash-based commitment
- 4.9 Polynomial commitment schemes
- 4.10 Secret sharing
- 5 Pseudorandom functions, block ciphers, and format-preserving encryption
- 6 Symmetric encryption, AEAD, and key derivation
-
7 Key agreement
- 7.1 The Diffie–Hellman protocol
- 7.2 Static and ephemeral keys
- 7.3 The key-agreement scheme abstraction
- 7.4 Passive security and the Diffie–Hellman assumptions
- 7.5 Active attacks and the role of authentication
- 7.6 Elliptic-curve Diffie–Hellman
- 7.7 Hybrid public-key encryption
- 7.8 Key privacy
- 7.9 Shielded-note delivery as deployed hybrid encryption
-
8 Digital signatures
- 8.1 Signatures versus MACs
- 8.2 Syntax and security goal
- 8.3 The hash-and-sign paradigm
- 8.4 The Schnorr identification protocol
- 8.5 From identification to signature via the Fiat–Shamir transform
- 8.6 Security in the random oracle model and the forking lemma
- 8.7 RedDSA: re-randomisable Schnorr for Orchard
- 8.8 Key re-randomisation and unlinkability
- 8.9 Binding signatures as a proof of knowledge of a discrete logarithm
- 8.10 The transparent layer’s schemes: ECDSA and BIP-340 over secp256k1
-
9 Interactive proofs, zero knowledge, and SNARKs
- 9.1 Soundness, zero knowledge, and succinctness
- 9.2 Languages, relations, and witnesses
- 9.3 Interactive protocols, proofs, and arguments
- 9.4 Knowledge soundness and extractors
- 9.5 The simulation paradigm and zero knowledge
- 9.6 Sigma-protocols
- 9.7 The Fiat–Shamir transform: from interactive to non-interactive
- 9.8 SNARKs: succinct non-interactive arguments of knowledge
-
10 Merkle trees and commitments to sets
- 10.1 Two statements about a set
- 10.2 The compression function and collision resistance
- 10.3 Binary Merkle trees
- 10.4 Authentication paths and membership proofs
- 10.5 Soundness: forging a path implies a collision
- 10.6 Layer and domain separation
- 10.7 Append-only and incrementally updatable trees
- 10.8 Vector commitments
- 10.9 Privacy-preserving membership via zero-knowledge paths
- 10.10 A shielded spend, end to end