The Zcash ArboretumII Crypto Guide
Contents
PDF
Theme

6 Symmetric encryption, AEAD, and key derivation

This section defines symmetric encryption, message authentication codes, authenticated encryption with associated data (AEAD), and key-derivation functions, each with its security notion. It proves that encrypt-then-MAC composes a cipher secure against chosen-plaintext attack and a strongly unforgeable MAC with independent keys into an AEAD (Theorem 6.16), and that ChaCha20-Poly1305, the AEAD of Zcash note encryption, is secure for a uniform key and non-repeating nonces if ChaCha20 is a pseudorandom function (Theorem 6.20); a key-derivation function derives that key from a Diffie–Hellman shared secret. The adversary controls the channel: it sees every ciphertext, and may modify, splice, or replay ciphertexts in transit.

Throughout, an adversary is a probabilistic algorithm 𝒜; the notation y←𝒜(x) denotes running 𝒜 on input x and assigning its output to y, and x←$S denotes sampling x uniformly from the finite set S. Every adversary in the computational definitions is probabilistic polynomial time (PPT) in the security parameter λ, and negl(λ) denotes a negligible function (Math Guide, §“Polynomial, exponential, and negligible functions”; recalled in §1.2).

The one-time pad and EAV security.

The information-theoretic baseline is the one-time pad: to encrypt m∈{0,1}L under a uniformly random key k∈{0,1}L used exactly once, output c=m⊕k. Since m⊕k is uniform for every m, the ciphertext distribution is independent of the message, and even an unbounded eavesdropper learns nothing—Shannon’s perfect secrecy. The cost is twofold: the key must be as long as the message, and it must never be reused, for two ciphertexts under one pad reveal c⊕c′=m⊕m′ to any observer of both—the two-time-pad failure. The computational relaxation is EAV security (security against an eavesdropper): an adversary who chooses two equal-length messages m0,m1 and sees a single ciphertext Enck(mb) for a hidden uniform bit b guesses b with advantage at most negl(λ)—the one-ciphertext, no-oracle restriction of the chosen-plaintext game formalised in §6.2. Replacing the truly random pad by the output of a pseudorandom generator stretched from a short seed—the pseudo-one-time pad—achieves EAV security with a fixed-length key, at the cost of resting on a pseudorandomness assumption.

6.1 Stream ciphers and ChaCha20

A stream cipher is the practical instantiation of the pseudo-one-time pad: a keyed, seekable generator producing a keystream that XORs into the plaintext. To encrypt many messages under one key without violating the one-time-pad no-reuse rule, modern stream ciphers take an additional public input called a nonce (number used once) and behave like a pseudorandom function of the nonce, in the sense of Section 5.

Definition 6.1 (Nonce-based stream cipher).

A nonce-based stream cipher is a deterministic function

KS:𝒦×𝒩×ℕ→{0,1}∗

producing, for key k, nonce ν, and length L, a keystream KS(k,ν,L)∈{0,1}L. Encryption of m∈{0,1}L is Enck(ν,m)=m⊕KS(k,ν,|m|) with ciphertext (ν,c); decryption recomputes the keystream and XORs it off. The security goal is that for distinct nonces the keystreams are jointly indistinguishable from independent uniform strings, provided no nonce repeats under a fixed key.

The stream cipher Zcash deploys—inside the AEAD of §6.5, in the note-encryption layer—is ChaCha20, designed by Bernstein and standardised in RFC 8439. Its core is a reversible mixing of four 32-bit words built only from modular addition, XOR, and rotation (an “ARX” design), which avoids data-dependent table lookups and hence the timing side channels that table-based ciphers must otherwise mitigate.

Construction 6.2 (ChaCha20).

The ChaCha20 state is a 4×4 matrix of 32-bit words, viewed as a vector (x0,…,x15)∈(ℤ/232⁢ℤ)16; the symbol + denotes addition modulo 232, ⊕ XOR, and x⋘r left rotation by r bits. The quarter-round QR(a,b,c,d) updates four words by

a +=b; d ⊕=a; d ⋘=16;
c +=d; b ⊕=c; b ⋘=12;
a +=b; d ⊕=a; d ⋘=8;
c +=d; b ⊕=c; b ⋘=7.

The state is initialised from the 128-bit constant “expand 32-byte k” (words x0–x3), a 256-bit key (x4–x11), a 32-bit block counter (x12), and a 96-bit nonce (x13–x15). One double round applies QR to the four columns and then to the four diagonals; the 20 rounds of ChaCha20 are ten double rounds. Writing X for the initial state and R(X) for the state after the rounds, the 64-byte keystream block is the feed-forward sum R(X)+X (word-wise, modulo 232), serialised in little-endian order.

Remark 6.3 (Feed-forward and counter mode).

The rounds R form a bijection—each quarter-round is invertible, being a composition of invertible word operations—so without the final addition the block function would be an invertible permutation, and an adversary holding a keystream block could run the rounds backwards. The feed-forward sum R(X)+X destroys invertibility; it is the standard Davies–Meyer-style construction of a one-way mixing function from a permutation. Incrementing the block counter x12 produces successive 64-byte keystream blocks, so KS(k,ν,L) is the concatenation of the blocks for counters 0,1,2,…; this counter mode is what makes the cipher seekable and parallelisable. Like every concrete cipher of Section 5, ChaCha20 is only conjectured to be a secure PRF of the pair (nonce, counter); no attack better than brute force over the 256-bit key is known. Reusing a (k,ν) pair reproduces the same keystream and re-creates the two-time-pad failure, so nonce uniqueness is a hypothesis of the security claim.

6.2 Chosen-plaintext security

Security against chosen-plaintext attack (CPA) extends EAV security to an adversary that influences which messages are encrypted—by triggering payments, injecting plaintext into a session, or guessing—and observes many ciphertexts. It is modelled by oracle access to the encryption algorithm in the game template of Definition 1.15.

Definition 6.4 (CPA security).

For a symmetric encryption scheme Π with key generator Gen, adversary 𝒜, and bit b∈{0,1}, the game 𝖢𝖯𝖠Π𝒜(λ,b) runs as follows.

  1. 1.

    The challenger samples k←Gen(1λ) and gives 𝒜 oracle access to Enck(⋅).

  2. 2.

    At some point 𝒜 submits a challenge pair (m0,m1) of equal-length messages and receives c⋆←Enck(mb).

  3. 3.

    The adversary may continue querying the oracle and finally outputs a bit b′, which is the output of the game.

The scheme Π is CPA-secure if for every PPT 𝒜,

AdvΠcpa(𝒜,λ):=|Pr[𝖢𝖯𝖠Π𝒜(λ,0)=1]−Pr[𝖢𝖯𝖠Π𝒜(λ,1)=1]|∈negl(λ).
Proposition 6.5 (Determinism precludes CPA security).

No scheme whose Enc is deterministic and stateless is CPA-secure.

Proof.

The adversary queries the oracle on two distinct messages m0≠m1, recording c0=Enck(m0) and c1=Enck(m1). Decryption correctness forces c0≠c1: a single ciphertext cannot decrypt to both messages. The adversary submits the challenge (m0,m1), receives c⋆=Enck(mb), and outputs 0 if c⋆=c0 and 1 otherwise. Since Enc is deterministic, c⋆=cb, and since c0≠c1 the comparison identifies b: the guess is always correct and the advantage is 1. □

A CPA-secure scheme must therefore be randomised or nonce-based. A nonce-based stream cipher used with a fresh nonce per encryption—random, or drawn from a counter—attains CPA security under the PRF conjecture for its keystream generator, because each encryption is then effectively a fresh one-time pad; for ChaCha20 the argument is the confidentiality part of the proof of Theorem 6.20.

Remark 6.6 (Semantic security).

Goldwasser and Micali’s original notion, semantic security, demands that whatever an efficient adversary can compute about the plaintext from the ciphertext, the adversary could have computed without the ciphertext, from the message length alone. Semantic security is provably equivalent to the indistinguishability notions above; we use indistinguishability because it is easier to manipulate in reductions.

6.3 Message authentication codes

CPA security implies nothing about integrity. A stream-cipher ciphertext is XOR-malleable: flipping a ciphertext bit flips the corresponding plaintext bit, so an adversary on the channel can turn a payment of one amount into a payment of another without the key. Detecting modification requires a second keyed primitive, directed against forgery rather than distinguishing: the shared-key message authentication code, which the AEAD requires.

Definition 6.7 (Message authentication code).

A message authentication code (MAC) is a pair (Mac,Vrfy) with key space 𝒦: algorithm Mack(m) outputs a tag t, and Vrfyk(m,t)∈{0,1} accepts (1) or rejects (0). Correctness requires Vrfyk(m,Mack(m))=1 for all k,m. When Mac is deterministic, canonical verification recomputes the tag and checks equality.

Definition 6.8 (Existential and strong unforgeability).

For a MAC Π and adversary 𝒜, the game 𝖥𝗈𝗋𝗀𝖾Π𝒜(λ) runs as follows.

  1. 1.

    The challenger samples k←$𝒦 and gives 𝒜 oracle access to Mack(⋅); let Q be the set of messages queried.

  2. 2.

    The adversary outputs a pair (m⋆,t⋆); the game outputs 1 iff Vrfyk(m⋆,t⋆)=1 and m⋆∉Q.

The MAC is existentially unforgeable under chosen-message attack (EUF-CMA) if for every PPT 𝒜,

AdvΠforge⁢(𝒜,λ):=Pr⁡[𝖥𝗈𝗋𝗀𝖾Π𝒜⁢(λ)=1]∈negl⁡(λ).

A strongly unforgeable (sUF-CMA) MAC additionally forbids producing a new valid tag on an already-queried message: the adversary wins on (m⋆,t⋆) as long as the oracle never returned that exact pair. We write AdvΠs⁢-⁢forge(𝒜,λ) for the advantage in this variant.

The MAC Zcash uses, Poly1305, is not a pseudorandom-function MAC but a one-time, universal-hash MAC: it provides information-theoretic security per nonce and is fast, at the cost of a key that authenticates only a single message. Its security rests on a hash family whose differences are unpredictable.

Definition 6.9 (ε-almost-Δ-universal hash family).

Let (𝒢,+) be a finite abelian group. A family of functions {hr:𝒳→𝒢}r∈ℛ is ε-almost-Δ-universal (ε-AΔU) if for all distinct x,x′∈𝒳 and every δ∈𝒢,

Prr←$ℛ⁡[hr⁢(x)−hr⁢(x′)=δ]≤ε.

Taking δ=0 recovers ordinary ε-universality—low collision probability—while the Δ condition controls additive differences, which is what makes the one-time MAC below secure. With 𝒢={0,1}n under XOR this is the classical almost-XOR-universality; Poly1305 takes 𝒢=ℤ/2128ℤ under addition modulo 2128.

The Carter–Wegman paradigm turns any AΔU family into a one-time MAC by masking the hash value with a fresh uniform pad.

Theorem 6.10 (Carter–Wegman one-time MAC).

Let {hr} be ε-AΔU into (𝒢,+). Define a MAC with key (r,s), where r←$ℛ and the pad s←$𝒢, by Macr,s(m)=hr(m)+s. If (r,s) authenticates at most one message, then any adversary—even a computationally unbounded one—who sees one message–tag pair (m,t) forges a valid pair (m⋆,t⋆) with m⋆≠m with probability at most ε.

Proof.

The adversary observes t=hr(m)+s and must output (m⋆,t⋆) with m⋆≠m and t⋆=hr(m⋆)+s. Subtracting the two tag equations eliminates the pad: the forgery succeeds iff

hr⁢(m⋆)−hr⁢(m)=t⋆−t.

Condition on the adversary’s view. The pad s is uniform and independent of r, so given the single observed tag t, every value of hr(m) is equally consistent—each candidate value determines a unique s—and the observation therefore leaks nothing about r: the posterior on r remains uniform on ℛ. The adversary’s difference δ:=t⋆−t and distinct pair (m,m⋆) are thus fixed independently of r, and the AΔU property gives Pr[hr(m⋆)−hr(m)=δ]≤ε. □

The MAC Poly1305 instantiates the paradigm with a polynomial-evaluation hash over the prime field 𝔽p for p=2130−5 (prime-field arithmetic as in the Math Guide, §“The prime field and two inversion routes”).

Construction 6.11 (Poly1305).

Fix the prime p=2130−5 and work in 𝔽p. The key is a pair (r,s): r is a 128-bit value subjected to a fixed bit-clamping (the top four bits of bytes 3,7,11,15 and the bottom two bits of bytes 4,8,12 are forced to zero), and s is a 128-bit pad. To authenticate a message, split it into ℓ blocks c1,…,cℓ of at most 16 bytes; encode each block as an integer in [0,2128) and add 28⁢b, where b is the block’s byte length—this sets a 1 bit immediately above the block’s bytes, making every coefficient nonzero and the block encoding injective in both content and byte length. Interpreting r and each ci as elements of 𝔽p, the hash is the polynomial evaluation

hr⁢(m)=∑i=1ℓci⁢rℓ−i+1∈𝔽p,

computed by Horner’s rule as (⋯((c1r+c2)r+c3)r⋯)r. The tag is

Macr,s⁢(m)=((hr⁢(m)modp)+s)mod2128,

the field hash reduced and added to the pad modulo 2128.

Proposition 6.12 (Poly1305 is almost-Δ-universal).

Restricted to messages of at most L bytes—hence at most ℓmax=⌈L/16⌉ blocks—the reduced Poly1305 hash family {m↦hr(m)modp}, read into ℤ/2128ℤ, is ε-almost-Δ-universal with respect to addition modulo 2128, with

ε≤8⁢ℓmax2106.

The loss over the ideal ℓmax⋅p−1 accounts for the clamping of r—which restricts r to a subset of size 2106—and for the final reduction modulo 2128.

Proof.

Sketch. Fix two distinct messages m,m′ with block encodings (ci) and (c′j), padded to a common length ℓ≤ℓmax by leading zero coefficients without changing their values. The block encoding guarantees that m≠m′ yields distinct coefficient vectors: genuine coefficients are nonzero, so differing block counts set a nonzero coefficient against a zero padding one, while equal block counts leave two blocks differing in content or in final-block byte length, hence in encoding. The difference of hashes is

hr(m)−hr(m′)=∑i=1ℓ(ci−c′i)rℓ−i+1=:P(r)∈𝔽p,

a nonzero polynomial in r of degree at most ℓ. It remains to count the values of r that attain a target difference δ∈ℤ/2128ℤ. The reduced hash values lie in [0,p), so their integer difference lies in the interval (−p,p), which has length 2p<8⋅2128; each residue class modulo 2128 therefore contains at most ⌈2p/2128⌉=8 candidate integer differences u. For each such u, the equation P(r)=u in 𝔽p has at most ℓ roots—a polynomial of degree ≤ℓ over a field has at most ℓ roots (Math Guide, §“Roots and the factor theorem”)—so at most 8ℓ values of r produce the difference δ. The clamped r is uniform over a set of 2106 values (clamping zeroes 22 of the 128 bits), so it equals one of those roots with probability at most 8ℓ/2106≤8ℓmax/2106. □

For messages of 16 384 bytes (ℓmax=1024 blocks) the bound gives ε≤8⋅1024/2106=2−93, against the ideal ℓmax/p≈2−120; the clamping and reduction losses cost 27 bits. By Proposition 6.12 and the Carter–Wegman Theorem 6.10, Poly1305 with a fresh, uniformly random pad s per message is a one-time MAC with forgery probability at most 8ℓmax/2106 per verification attempt; the pad must be uniform, not merely unpredictable, because the pad-elimination step of the theorem uses uniformity. In the AEAD below, ChaCha20 generates the one-time key (r,s) pseudorandomly from the nonce—uniformly once the cipher is idealised as a random function—so the guarantee holds per nonce.

6.4 Authenticated encryption with associated data

Authenticated encryption combines the two guarantees: the adversary learns nothing about plaintexts (CPA security) and cannot produce a new ciphertext that decrypts to anything other than the rejection symbol ⊥, a value distinct from every message (ciphertext integrity). The associated data is public context—packet headers, version bytes, an ephemeral public key—that travels in the clear but is authenticated with the ciphertext, so that the ciphertext cannot be replayed under a different context.

Definition 6.13 (AEAD scheme).

An authenticated encryption with associated data (AEAD) scheme is a pair (Enc,Dec) with key space 𝒦, nonce space 𝒩, and associated-data space 𝒟: algorithm Enck(ν,a,m) returns a ciphertext c, and Deck(ν,a,c) returns a message or ⊥. Correctness: Deck(ν,a,Enck(ν,a,m))=m for all k,ν,a,m. The scheme authenticates but does not encrypt the associated data a.

Definition 6.14 (Ciphertext integrity, INT-CTXT).

For an AEAD scheme Π and adversary 𝒜, the game 𝖢𝗍𝗑𝗍Π𝒜(λ) runs as follows.

  1. 1.

    The challenger samples k←$𝒦 and gives 𝒜 two oracles: an encryption oracle Enck(⋅,⋅,⋅), recording the set Q of returned triples (ν,a,c), and a verification oracle that on (ν,a,c) returns 1 if Deck(ν,a,c)≠⊥ and 0 otherwise. The adversary must never repeat a nonce to the encryption oracle (the nonce-respecting model); verification queries may reuse nonces freely.

  2. 2.

    The game outputs 1 iff some verification query (ν⋆,a⋆,c⋆)∉Q is answered 1.

The scheme Π has ciphertext integrity if for every PPT 𝒜, Pr[𝖢𝗍𝗑𝗍Π𝒜(λ)=1]∈negl(λ).

Definition 6.15 (Authenticated encryption).

An AEAD scheme is secure (is an AEAD) if it is both CPA-secure and has ciphertext integrity (Definition 6.14), where the CPA game of Definition 6.4 is run with k←$𝒦 and extended so that the adversary supplies the nonce and associated data of every oracle query and of the challenge, subject to the nonce-respecting restriction—a restriction on the adversary, not a property of the scheme—that no nonce is used twice across oracle queries and challenge. The restriction is necessary: an AEAD may encrypt deterministically given (ν,a,m)—ChaCha20-Poly1305 does—and then querying the oracle at (ν,a,m0) and submitting the challenge (ν,a,m0,m1) would identify the bit by comparing ciphertexts.

The standard route from a CPA-secure cipher and a strongly unforgeable MAC to an AEAD is encrypt-then-MAC: encrypt the message, compute a MAC over the ciphertext together with the associated data and nonce, and append the tag; decryption verifies the tag before decrypting, and any tag failure returns ⊥. The other orders, MAC-then-encrypt and encrypt-and-MAC, do not generically achieve authenticated encryption.

Theorem 6.16 (Encrypt-then-MAC yields authenticated encryption).

Let ΠE=(Enc,Dec) be a CPA-secure encryption scheme and ΠM=(Mac,Vrfy) a strongly unforgeable (sUF-CMA) MAC, with independent keys kE,kM. Define the composite scheme Π′ by

Enc′kE,kM⁢(ν,a,m)=(c,t),c←EnckE⁢(ν,m),t←MackM⁢(ν⁢‖a‖⁢c),

with Dec′ returning ⊥ unless VrfykM(ν‖a‖c,t)=1, in which case it returns DeckE(ν,c). Then Π′ is a secure AEAD: it is CPA-secure and has ciphertext integrity.

Proof.

Ciphertext integrity. Suppose a PPT 𝒜 making at most qv verification queries wins the game: some fresh query (ν⋆,a⋆,(c⋆,t⋆))∉Q decrypts successfully, i.e. VrfykM(ν⋆‖a⋆‖c⋆,t⋆)=1. Each encryption-oracle call on (ν,a,m) returned (c,t) and corresponds to one MAC query on the string w=ν‖a‖c returning tag t. Because the framing ν‖a‖c parses uniquely (the component lengths are fixed or prepended), the freshness of (ν⋆,a⋆,c⋆) means the MAC oracle never produced the string–tag pair (w⋆,t⋆) with w⋆:=ν⋆‖a⋆‖c⋆: either w⋆ was never queried, or it was queried and returned a different tag. Either way (w⋆,t⋆) is a fresh valid pair—a strong forgery against ΠM. The reduction ℬ runs 𝒜, answering encryption queries with its own MAC oracle and a self-chosen kE. Lacking kM, the reduction ℬ cannot answer verification queries, so it guesses: it samples a uniform index i≤qv in advance, answers each fresh verification query before the i-th with 0 (queries on triples in Q are answered 1, correctly), halts at the i-th fresh query, and outputs that query’s (w⋆,t⋆) as its forgery. On the event that 𝒜 wins and i indexes the first successful fresh query of 𝒜—the guess is right with probability 1/qv—every earlier 0 answer was correct, the simulation is perfect, and ℬ wins, so

Pr⁡[𝖢𝗍𝗑𝗍Π′𝒜⁢(λ)=1]≤qv⋅AdvΠMs⁢-⁢forge⁢(ℬ,λ)∈negl⁡(λ),

the factor qv being polynomial.

CPA security. The tag is computed from c (together with kM,ν,a, and the MAC’s own coins) and so carries no information about the challenge bit beyond what c already carries. Formally, the reduction ℬ′ samples kM itself, forwards 𝒜’s oracle and challenge queries to its own ΠE oracle to obtain the c-components, and appends tags it computes with kM. This simulates Π′ perfectly, so AdvΠ′cpa(𝒜,λ)=AdvΠEcpa(ℬ′,λ)∈negl(λ). □

Remark 6.17 (Why the ordering matters).

Encrypt-then-MAC rejects forged ciphertexts without decrypting: a rejected ciphertext never reaches the decryption logic, which therefore cannot leak, and this blocks chosen-ciphertext and padding-oracle attacks. MAC-then-encrypt verifies only after decrypting, exposing the decryption routine to attacker-chosen ciphertexts, which has historically been the source of many padding-oracle attacks. An authenticated-encryption scheme is also secure against chosen-ciphertext attack (CCA), whose game is the CPA game of Definition 6.4 with a decryption oracle added that refuses only the challenge ciphertext: by ciphertext integrity, every ciphertext the adversary did not legitimately obtain decrypts to ⊥ except with negligible probability, so the oracle is of no use.

6.5 The ChaCha20-Poly1305 AEAD

The scheme ChaCha20-Poly1305 (RFC 8439) is the AEAD by which Zcash encrypts every shielded note ciphertext and outgoing ciphertext (protocol specification, §“Symmetric Encryption”). It is an encrypt-then-MAC composition of the ChaCha20 stream cipher with the Poly1305 one-time MAC, in which the cipher derives both the keystream and the one-time MAC key from the single (k,ν) input.

Construction 6.18 (ChaCha20-Poly1305).

Fix a 256-bit key k and a 96-bit nonce ν. Encryption of a message m with associated data a proceeds as follows.

  1. 1.

    One-time MAC key. Run ChaCha20 with key k, nonce ν, and block counter 0; take the first 32 bytes of the keystream block as the Poly1305 one-time key (r,s)—clamp the first 16 bytes to form r; the next 16 are s. Discard the rest of this block.

  2. 2.

    Encrypt. Run ChaCha20 with key k and nonce ν starting at block counter 1, producing the keystream KS1 (the keystream of Remark 6.3 taken from counter 1 onward), and set c=m⊕KS1(k,ν,|m|).

  3. 3.

    Authenticate. Form the Poly1305 input by concatenating: a padded with zeros to a 16-byte boundary, c padded with zeros to a 16-byte boundary, the 8-byte little-endian length of a, and the 8-byte little-endian length of c. Compute the tag t=Poly1305r,s(that input).

The ciphertext is (c,t). Decryption recomputes (r,s) and the tag from (k,ν,a,c), compares it to t in constant time, returns ⊥ on mismatch, and otherwise outputs m=c⊕KS1(k,ν,|c|).

Figure 9 draws the dataflow of the construction.

Refer to caption
Figure 9: The scheme ChaCha20-Poly1305 of Construction 6.18. The ChaCha20 block function (blue) on the key k (red) and nonce ν yields one 64-byte block per counter j. Block 0 (amber) is the one-time Poly1305 key: its first 16 bytes, clamped, form r, the next 16 form s, and the last 32 are discarded. The blocks from counter 1 on form the keystream KS1, XORed into m to give c. The Poly1305 MAC (amber) hashes, under r, the zero-padded a and c followed by their 8-byte little-endian lengths, and adds the pad s modulo 2128 to give the tag t; the ciphertext is (c,t) (green). Reserving counter 0 for the MAC key is domain separation: the MAC key and the keystream are outputs of the cipher at distinct counters (Remark 6.21).
Remark 6.19 (Length encoding prevents splicing).

Without the trailing 8-byte lengths of a and c, the zero-padding that aligns a and c to 16-byte boundaries would let an adversary shift bytes between the associated data and the ciphertext, or pad-extend one of them, while leaving the Poly1305 input string unchanged—breaking the binding between a and c even though every authenticated byte is intact. Appending the explicit lengths makes the MAC input an injective encoding of the pair (a,c), the same injectivity that the per-block length encoding supplies within one message in the AΔU analysis (Proposition 6.12).

Theorem 6.20 (Security of ChaCha20-Poly1305).

Model ChaCha20 as a pseudorandom function Fk(ν,j) from (nonce, block counter) pairs to 64-byte blocks. In the nonce-respecting model, ChaCha20-Poly1305 is a secure AEAD. Concretely, consider a PPT adversary making q encryption queries and qv verification queries, each of whose Poly1305 inputs—padded associated data, padded ciphertext, and the length block—comprises at most ℓmax sixteen-byte blocks, ℓmax=⌈|a|/16⌉+⌈|c|/16⌉+1. The adversary’s CPA advantage is at most twice the best PRF-distinguishing advantage against F at comparable cost, and the adversary forges—wins the INT-CTXT game—with probability at most

AdvFprf⁢(ℬ,λ)+8⁢qv⁢ℓmax2106,

where ℬ is a PRF distinguisher of comparable cost.

Proof.

Sketch. Replace Fk by a truly random function Φ from (nonce, counter) pairs to 64-byte blocks. Any noticeable change in the adversary’s success probability yields a PRF distinguisher of comparable cost—it simulates the whole game using its function oracle—so each replacement costs one AdvFprf term; the CPA game is played twice (once per challenge bit), whence the factor two there. We analyse the idealised scheme.

Confidentiality. Since the adversary is nonce-respecting, every encryption query uses a fresh ν, and the keystream blocks Φ(ν,1),Φ(ν,2),… are uniform and independent of everything else in the adversary’s view; the ciphertext c=m⊕KS is a one-time pad encryption and reveals nothing about m beyond its length. The tag is a deterministic function of c,a,ν and the (independent) key (r,s), and adds no information. The idealised CPA advantage is therefore zero.

Integrity. For each nonce ν, the block Φ(ν,0)[0:32] is uniform and independent across distinct nonces; clamping its first half samples r from Poly1305’s prescribed restricted set, while the second half s stays uniform, so the resulting one-time keys are independent across nonces. Because counter 0 is reserved for this key while encryption consumes counters ≥1, each one-time key is also independent of the keystream that produced its ciphertext. Per nonce, the setting is exactly the Carter–Wegman one-time MAC of Theorem 6.10 instantiated with the ε-AΔU Poly1305 hash of Proposition 6.12, ε≤8ℓmax/2106. Consider any single fresh verification query (ν⋆,a⋆,c⋆,t⋆). If ν⋆ was never used for encryption, the pad s for ν⋆ is uniform and entirely unknown, so the tag is correct with probability 2−128. If ν⋆ equals the nonce of some encryption query—nonce reuse is allowed in verification queries, only encryption is nonce-respecting— then the adversary has seen exactly one tag under that (r,s), and freshness of (a⋆,c⋆) makes this a forgery on a new message under a one-time key, succeeding with probability at most ε by Theorem 6.10. The union bound over the qv verification queries (Math Guide, §“The union bound and a birthday calculation”) gives forgery probability at most 8qvℓmax/2106 in the idealised scheme; adding back the PRF-switching cost yields the stated bound. □

Remark 6.21 (One key for encryption and authentication).

The scheme reuses one 256-bit key for both encryption and authentication, seemingly violating the independent-keys hypothesis of Theorem 6.16. Reserving block counter 0 for the Poly1305 key and counters ≥1 for the keystream restores independence: once the cipher is idealised as a truly random function—the switch the proof of Theorem 6.20 pays for with a PRF-distinguishing term—outputs at distinct counters are independent, so (r,s) is independent of the keystream and the two-key analysis applies. For the PRF itself the independence is computational, not literal. Domain separation by a counter or label, the discipline of §3.5, is the general pattern by which one master key safely serves several roles.

Remark 6.22 (Wrong-key rejection and key commitment).

Later volumes use this AEAD in a trial-decryption pattern: a receiver detects the notes addressed to it by attempting decryption of every ciphertext under each of its keys, relying on decryption under a wrong key to return ⊥ (protocol specification, §“Symmetric Encryption”). The scheme provides this for honestly produced ciphertexts. Fix a ciphertext (c,t)=Enck(ν,a,m) and a key k′ independent of k, and idealise the cipher under k and under k′ as independent random functions, as in the proof of Theorem 6.20. The one-time key (r′,s′) that decryption under k′ derives from block (ν,0) is then uniform and independent of (c,t): the pad s′ alone makes the recomputed tag match t with probability exactly 2−128, and even conditioned on one exposed tag under (r′,s′), Theorem 6.10 bounds acceptance by the AΔU slack 8ℓmax/2106 of Proposition 6.12, with ℓmax as in Theorem 6.20. Decryption under an independent key therefore rejects except with probability at most 2−128+8ℓmax/2106 per attempt, plus two PRF-distinguishing terms for the two idealisations.

The guarantee does not extend to malicious senders: CPA security and INT-CTXT are single-key notions, and nothing in Definition 6.15 constrains a ciphertext crafted by a sender who knows several keys. The scheme is not key-committing—the separate notion demanding that no ciphertext verify under two distinct keys—and a sender who chooses keys k1,k2 can craft a single (c,t) that decrypts validly, to different plaintexts, under both: with (ri,si) the one-time key each ki derives, the hash hri of Construction 6.11 is linear in the blocks of c, so fixing t, leaving two blocks of c free, and solving over 𝔽p the two linear equations that pin the hash under ri to t−si (retrying until both solutions encode valid blocks) makes both keys accept (c,t)—the multi-key collision of Len, Grubbs, and Ristenpart’s partitioning-oracle attack. The trial-decryption arguments of later volumes therefore never rest on the tag alone against adversarial senders: their note-plaintext consistency checks—recomputing the note commitment from the decrypted plaintext and comparing it against the commitment the transaction carries—close this gap.

6.6 Key-derivation functions

Theorem 6.20 assumes a uniformly random 256-bit key; its proof does not apply to a non-uniform key, whose structure the adversary may exploit. A Diffie–Hellman shared secret is high-entropy but not uniform: a structured group encoding, not a uniform bit string; a hardware noise source may likewise spread its unpredictability unevenly across its bits. A key-derivation function (KDF) converts such a source secret into one or more pseudorandom keys; the entropy of the source is measured worst-case, not average-case. (A passphrase is a usually low-entropy source and needs a deliberately costly password KDF instead.)

Definition 6.23 (Min-entropy).

The min-entropy of a random variable X is

H∞⁢(X)=−log2⁡maxx⁡Pr⁡[X=x];

equivalently, the best chance of guessing X in one try is 2−H∞⁢(X). Given side information Z, the conditional min-entropy is

H~∞⁢(X∣Z)=−log2⁡𝔼z←Z⁢maxx⁡Pr⁡[X=x∣Z=z],

so that 2−H~∞⁢(X∣Z) is the best chance of guessing X from Z. Recall the statistical distance Δ(X,Y)=12∑u|Pr[X=u]−Pr[Y=u]| of Definition 1.6 (Math Guide, §“Statistical distance”); we say X is ϵ-close to uniform on a set S if Δ(X,US)≤ϵ.

Definition 6.24 (Key-derivation function and its security).

A key-derivation function is a function

KDF:𝒳×ℐ×{0,1}∗×ℕ→{0,1}∗

taking a source secret (a sample of a random variable Σ over 𝒳), a non-secret salt slt∈ℐ, an info or context string ctx, and a desired output length L. The security goal must specify the source model. For an arbitrary source of conditional min-entropy at least γ given the adversary’s side information, an extractor-style guarantee uses a salt sampled uniformly and independently of the source and requires the pair (slt,KDF(Σ,slt,ctx,L)) to be computationally indistinguishable from (slt,UL), even given ctx and that side information. No fixed deterministic unsalted function can provide this guarantee for every high-min-entropy source; an unsalted KDF therefore rests on a narrower premise, such as input keying material that is already computationally pseudorandom, or that is hard to query in a random-oracle model.

The notion a KDF targets is that of a seeded randomness extractor whose output need only be computationally indistinguishable from uniform.

Definition 6.25 (Strong computational extractor).

A keyed function Ext:ℐ×𝒳→{0,1}n is a strong (γ,ϵ)-computational extractor if for every source Σ over 𝒳 of conditional min-entropy at least γ given auxiliary information Z, and a uniformly random salt slt←$ℐ, the pair (slt,Extslt(Σ)) is computationally indistinguishable from (slt,Un), even given Z, with distinguishing advantage at most ϵ. “Strong” means the salt is revealed to the distinguisher.

The leftover hash lemma realises the notion information-theoretically; the deployed mechanism below rests on random-oracle modelling instead.

Theorem 6.26 (Leftover hash lemma; stated without proof).

Let {gr:𝒳→{0,1}n} be a 2−n-universal hash family with a uniform public seed R. For any X with H∞(X)≥γ,

Δ⁢((R,gR⁢(X)),(R,Un))≤12⁢2n−γ.

Thus γ≥n+2log2(1/ϵ) bits of min-entropy yield n output bits that are ϵ-close to uniform—a strong (γ,ϵ)-extractor in the statistical, not merely computational, sense.

HKDF.

The standardised general-purpose KDF is Krawczyk’s HKDF (RFC 5869), built from HMAC (§5.3) in an extract-then-expand architecture: a salted HMAC call first distils suitable non-uniform input keying material into a short pseudorandom key (the extractor stage, justified along leftover-hash lines), and a counter-chained sequence of HMAC calls then expands that key, under a context string, up to RFC 5869’s limit of 255 hash-output-length blocks (the expander stage, justified by HMAC’s PRF security). The guarantee of HKDF depends on assumptions about the source and about HMAC. Zcash does not use it, because the protocol’s requirements are narrower and a single hash call meets them in the random-oracle analysis. The shielded protocol uses HMAC nowhere: neither the orchard nor the zcash_note_encryption crate carries an HMAC dependency (HMAC enters the wallet stack through the transparent BIP-32 derivation and BIP-39 mnemonic layers and, transitively, through the optional Tor client, never through a shielded crate).

The Zcash KDF.

Orchard derives the note-encryption key by one personalised BLAKE2b call:

Kenc=KDF⁢(𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍,𝖾𝗉𝗄)=BLAKE2b⁢-⁢256⁢("Zcash_OrchardKDF";𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍∥𝖾𝗉𝗄),

where 𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍 is the Diffie–Hellman shared point of the note-encryption key agreement, 𝖾𝗉𝗄 is the sender’s ephemeral public key, and the quoted string occupies BLAKE2b’s 16-byte personalisation field (the input is the serialised shared point followed by the ephemeral-key bytes, and the output is 32 bytes; protocol specification, §“Orchard Key Derivation”). The analysis models this personalised hash as a random oracle: by the domain-separation principle of §3.5 (Proposition 3.17, via the native-personalisation idiom catalogued there), the personalisation makes it an oracle independent of every other hash use in the protocol, and the derived key is uniform in the adversary’s view unless the adversary queries that oracle at the hidden 𝗌𝗁𝖺𝗋𝖾𝖽𝖲𝖾𝖼𝗋𝖾𝗍—a query whose argument the adversary must first compute from the two public keys, an instance of the computational Diffie–Hellman problem of §2.2. Including 𝖾𝗉𝗄 in the input binds the derived key to this ephemeral key, the role the context string plays in HKDF. No salt is used because the claim is this narrower Diffie–Hellman-plus-random-oracle one—the unsalted premise of Definition 6.24—not extraction from every high-min-entropy source.

Remark 6.27 (The role of the KDF in the larger protocol).

In the Zcash note-encryption layer the shared secret is a point of the Pallas curve, and the key derived above is the uniform key that Theorem 6.20 assumes for ChaCha20-Poly1305. Section 7 composes the key agreement, this KDF, and the AEAD into hybrid public-key encryption.