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
The information-theoretic baseline is the one-time pad: to
encrypt
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.
A nonce-based stream cipher is a deterministic function
producing, for key , nonce , and length , a keystream
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 -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.
The ChaCha20 state is a
The state is initialised from the -bit constant
“expand 32-byte k” (words –), a
-bit key (–), a -bit block counter
(), and a -bit nonce (–). One
double round applies to the four columns and
then to the four diagonals; the rounds of ChaCha20
are ten double rounds. Writing for the initial state and
for the state after the rounds, the -byte keystream
block is the feed-forward sum
The rounds 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
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.
For a symmetric encryption scheme with key generator
, adversary , and bit
The challenger samples
At some point submits a challenge pair
of equal-length messages and receives
The adversary may continue querying the oracle and finally outputs a bit , which is the output of the game.
The scheme is CPA-secure if for every PPT ,
No scheme whose is deterministic and stateless is CPA-secure.
The adversary queries the oracle on two distinct messages
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.
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.
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.
A message authentication code (MAC) is a pair
with key space :
algorithm outputs a tag , and
For a MAC and adversary , the game runs as follows.
The challenger samples
The adversary outputs a pair ; the
game outputs iff
The MAC is existentially unforgeable under chosen-message attack (EUF-CMA) if for every PPT ,
A strongly unforgeable (sUF-CMA) MAC additionally forbids producing a new valid tag on an already-queried message: the adversary wins on as long as the oracle never returned that exact pair. We write 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.
Let
Taking
The Carter–Wegman paradigm turns any AU family into a one-time MAC by masking the hash value with a fresh uniform pad.
Let be -AU into
The adversary observes
Condition on the adversary’s view. The pad is uniform and
independent of , so given the single observed tag , every
value of is equally consistent—each candidate value
determines a unique —and the observation therefore leaks
nothing about : the posterior on remains uniform on
. The adversary’s difference
The MAC Poly1305 instantiates the paradigm with a
polynomial-evaluation hash over the prime field for
Fix the prime
computed by Horner’s rule as
the field hash reduced and added to the pad modulo .
Restricted to messages of at most bytes—hence at most
The loss over the ideal
Sketch. Fix two distinct messages
a nonzero polynomial in of degree at most . It remains
to count the values of that attain a target difference
For messages of bytes
(
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.
An authenticated encryption with associated data (AEAD)
scheme is a pair with key space
, nonce space , and associated-data
space : algorithm
returns a ciphertext , and
returns a message or . Correctness:
For an AEAD scheme and adversary , the game runs as follows.
The challenger samples
The game outputs iff some verification query
The scheme has ciphertext integrity if for every PPT
,
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
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.
Let
with returning unless
Ciphertext integrity. Suppose a PPT making at
most verification queries wins the game: some fresh query
the factor being polynomial.
CPA security. The tag is computed from (together with
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.
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 input.
Fix a -bit key and a -bit nonce . Encryption of a message with associated data proceeds as follows.
One-time MAC key. Run ChaCha20 with key , nonce , and block counter ; take the first bytes of the keystream block as the Poly1305 one-time key —clamp the first bytes to form ; the next are . Discard the rest of this block.
Encrypt. Run ChaCha20 with key and nonce
starting at block counter , producing the keystream
(the keystream of
Remark 6.3 taken from counter
onward), and set
Authenticate. Form the Poly1305 input by
concatenating: padded with zeros to a -byte boundary,
padded with zeros to a -byte boundary, the -byte
little-endian length of , and the -byte little-endian
length of . Compute the tag
The ciphertext is . Decryption recomputes and
the tag from , compares it to in
constant time, returns on mismatch, and otherwise
outputs
Figure 9 draws the dataflow of the construction.
Without the trailing -byte lengths of and , the zero-padding that aligns and to -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 and even though every authenticated byte is intact. Appending the explicit lengths makes the MAC input an injective encoding of the pair , the same injectivity that the per-block length encoding supplies within one message in the AU analysis (Proposition 6.12).
Model ChaCha20 as a pseudorandom function
from (nonce, block counter) pairs to -byte blocks. In the
nonce-respecting model, ChaCha20-Poly1305 is a secure AEAD.
Concretely, consider a PPT adversary making encryption queries
and verification queries, each of whose Poly1305
inputs—padded associated data, padded ciphertext, and the length
block—comprises at most sixteen-byte blocks,
where is a PRF distinguisher of comparable cost.
Sketch. Replace by a truly random function from (nonce, counter) pairs to -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 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
Integrity. For each nonce , the block
The scheme reuses one -bit key for both encryption and
authentication, seemingly violating the independent-keys hypothesis
of Theorem 6.16. Reserving block counter for
the Poly1305 key and counters
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
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
Theorem 6.20 assumes a uniformly random -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.)
The min-entropy of a random variable is
equivalently, the best chance of guessing in one try is . Given side information , the conditional min-entropy is
so that is the best chance of
guessing from . Recall the statistical distance
A key-derivation function is a function
taking a source secret (a sample of a random variable over
), a non-secret salt
The notion a KDF targets is that of a seeded randomness extractor whose output need only be computationally indistinguishable from uniform.
A keyed function
The leftover hash lemma realises the notion information-theoretically; the deployed mechanism below rests on random-oracle modelling instead.
Let
Thus
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 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).
Orchard derives the note-encryption key by one personalised BLAKE2b call:
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 -byte personalisation field (the input is the serialised shared point followed by the ephemeral-key bytes, and the output is 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.