This section defines pseudorandom functions (PRFs), pseudorandom permutations, and strong pseudorandom permutations, each by a game in which an adversary queries a black box adaptively and outputs one bit guessing whether a short secret key drives the box or the box is a uniformly random function or permutation, in the strong case queried in both directions. The switching lemma (Lemma 5.9) bounds the cost of exchanging the two ideal objects. The section then constructs the instances the protocol uses: the block cipher AES; keyed and personalised BLAKE2, which supplies the PRFs inventoried in Remark 5.14; and the format-preserving cipher FF1, which builds a keyed bijection from a PRF that is not invertible and, on 11 -byte strings, derives Orchard’s address diversifiers. The next section builds from these primitives symmetric encryption, authentication, and the authenticated encryption that carries every shielded note.
Notation is that of the provable-security model. Strings of length
l form { 0, 1 } l , all finite strings form
{ 0, 1 } ∗ , and | x | is the length of x ; for a finite
set S , the notation
| Adv (A) = | Pr [A outputs 1 in Exp 1] − Pr [A outputs 1 in Exp 0] | |
between the two experiments the game distinguishes. Oracle access formalises the black box.
For a function f , the notation A f denotes an adversary granted oracle access to f : a black box to which A may submit inputs x of its choice, receiving f (x) in a single computation step, and from which it learns nothing about f beyond the answers to the queries it makes. The adversary’s running time always bounds the number of its oracle queries, which is hence polynomial in λ .
Pseudorandomness is measured against an ideal object, the “truly random function”.
Let Func (D, R) denote the set of all functions from a
finite set D to a finite set R . A random function from
D to R is an element
There are | R | | D | functions in Func (D, R) ,
an infeasibly large set for the domains of interest: for
A keyed function is a deterministic, efficiently computable map
| F : { 0, 1 } λ × { 0, 1 } l (λ) ⟶ { 0, 1 } m (λ), (k, x) ⟼ F k (x), |
where the input length l and output length m are
polynomially bounded functions of the key length λ . Fixing
the key k yields the function
Let F be a keyed function. The distinguishing game PRF F A (λ) runs as follows.
The challenger samples a bit
The adversary A (1 λ) , receiving the security parameter in unary to convey the parameter size, queries O adaptively.
The adversary outputs a bit b ′ ; the game outputs 1 iff
The family F is a pseudorandom function (PRF) if for every PPT adversary A ,
| Adv F prf (A, λ) := | Pr k ← $ { 0, 1 } λ [A F k (1 λ) = 1] − Pr R ← $ Func (l (λ), m (λ)) [A R (1 λ) = 1] | ∈ negl (λ) . |
The two probabilities are the adversary’s output distributions in the
worlds
The algorithm defining F is public; only the sampled key is hidden.
The restriction to efficient adversaries cannot be removed. As k ranges over its 2 λ values, the keyed function F k takes at most 2 λ distinct values in Func (D, R) —a vanishing fraction of all | R | | D | functions—so the two distributions of Definition 5.4 have statistical distance close to the maximum, and an unbounded adversary could distinguish them. Security therefore holds only against computationally bounded adversaries, as for the PRG separation in the proof of Proposition 1.10.
The adversary’s access is adaptive: later queries may depend on earlier answers, and downstream constructions rely on this. A non-adaptive definition, in which the adversary fixes all queries before seeing any answer, is strictly weaker: families exist that pass every non-adaptive test yet fall to an adaptive distinguisher.
Decryption requires each key to yield an invertible map, so a block cipher is a keyed permutation, measured against a random permutation.
A keyed function
Let F be a keyed permutation. The game
PRP F A (λ) is the game of
Definition 5.4 with the ideal world replaced: for
| Adv F prp (A, λ) := | Pr k [A F k (1 λ) = 1] − Pr P ← $ Perm (l) [A P (1 λ) = 1] | ∈ negl (λ) . |
A keyed permutation F is a strong pseudorandom permutation (SPRP) if no PPT adversary distinguishes even when granted oracle access to both the permutation and its inverse: for every PPT A ,
| Adv F sprp (A, λ) := | Pr k [A F k, F k − 1 (1 λ) = 1] − Pr P ← $ Perm (l) [A P, P − 1 (1 λ) = 1] | ∈ negl (λ) . |
A block cipher deployed where the adversary can obtain decryptions of chosen ciphertexts must be an SPRP, the standard security target for a block cipher.
On q distinct queries, a random function
Let
| | Pr P ← $ Perm (l) [A P = 1] − Pr R ← $ Func (l, l) [A R = 1] | ≤ q (q − 1) 2 l + 1 . |
We omit the proof, a game-hopping argument (Remark 1.18) that bounds the probability of an output collision among the q answers by the birthday count (q 2) / 2 l of Lemma 3.11, computed in the Math Guide (§“The union bound and a birthday calculation”).
Consequently, a secure PRP on a large domain is also a secure PRF while
the number of queries stays well below the birthday bound
2 l / 2 : the two advantages differ by at most
A block cipher with block length b and key length κ is a keyed permutation
| E : { 0, 1 } κ × { 0, 1 } b ⟶ { 0, 1 } b, |
together with its inverse
The asymptotic PRP definition concerns a family indexed by
λ ; a block cipher fixes b and κ —
A block cipher E is a (t, q, ε) -secure PRP if
every adversary running in time at most t and making at most q
oracle queries has
The Rijndael cipher of Daemen and Rijmen, standardised as AES in
FIPS 197, has block length
SubBytes, a nonlinear byte substitution—the
S-box—built on field inversion
ShiftRows, a transposition of bytes within the array;
MixColumns, an invertible column-wise linear mix; and
AddRoundKey, the XOR of a 128 -bit round key that a key schedule expands from k .
The first
The SPN design realises Shannon’s two principles. The nonlinear S-box supplies confusion: making the relationship between key and ciphertext as complex as possible. The ShiftRows and MixColumns layers supply diffusion: spreading the influence of each input bit over the whole output. Iterating the two for ten or more rounds gives AES its empirical resistance to all known attacks. No proof that AES is a PRP exists; like every practical block cipher, its security is a conjecture, corroborated by decades of failed cryptanalysis but resting on no reduction to a cleaner problem. Every downstream theorem therefore takes “ E is a PRP/SPRP” as an assumption, the status Remark 1.29 assigned to the concrete hash functions.
Hash functions are a second source of PRFs. The naive keying of a hash H by prepending the key,
| F k (m) = H (k ∥ m), |
is unsafe for the iterated Merkle–Damgård hashes (MD5, SHA-1, SHA-256)—which pad the message into blocks, fold the blocks one at a time into a fixed-width chaining state through a compression function, and emit the final state—because of the length-extension attack: from H (k ∥ m) and | m | alone, the adversary computes H (k ‖ m ‖ pad ∥ m ′) for a suffix m ′ of its choosing, without knowing k , since a Merkle–Damgård digest is the internal chaining state after absorbing k ∥ m , from which the adversary resumes the iteration. Used as a message authentication code (MAC)—a keyed function whose output tag certifies a message, defined under “Message authentication codes” in the next section—the naive construction thus yields a valid tag on m ‖ pad ‖ m ′ , a message the key holder never authenticated.
The classical remedy is HMAC, the nested double call
| HMAC k (m) = H ((k ⊕ opad) ∥ H ((k ⊕ ipad) ∥ m)) |
for two fixed pad constants: the inner hash absorbs the message under one key-derived value, and the outer hash re-keys the fixed-length result, so the emitted digest is no longer a resumable chaining state. Bellare’s analysis shows that HMAC is a PRF whenever the underlying compression function is, up to a birthday term q 2 / 2 l in the chaining-state length l ; as a PRF it is in particular a secure message authentication code, and it is the building block of the standardised key-derivation function HKDF, noted under “Key-derivation functions” in the next section. The shielded protocol does not use HMAC, because its hash admits direct keying.
Hash functions of the sponge family (Construction 3.26) and of the HAIFA family—the Merkle–Damgård variant whose compression function also takes the count of bits hashed so far, the lineage of BLAKE2—are not subject to length extension and so admit direct keying. The BLAKE2 design is built to be keyed natively: the construction loads the key length into its parameter block and prepends the key, padded to a full block, as the first message block, and its compression function mixes in a block counter and finalisation flags. (Its successor BLAKE3 is natively keyed too, by a different mechanism: the key words replace the initial state, and a dedicated flag marks the keyed mode.) The keyed function
| F k (m) = BLAKE2 (m ; key = k) |
is then a PRF directly, without a nested double call. No length-extension attack applies: the finalisation flag, XORed into the state for the last block, means the emitted digest is not the raw chaining value and cannot be used to resume the computation.
The Zcash protocol uses BLAKE2b and BLAKE2s through two parameters of the BLAKE2 design: the key, for PRF and MAC use as above, and the personalisation string, a domain-separation tag written into the initial state— 16 bytes for BLAKE2b, 8 bytes for BLAKE2s. Personalisation makes the same input hashed for two purposes—nullifier derivation versus note-commitment derivation, for example—yield independent-looking outputs, so each use site is effectively an independent PRF. This realises the independent oracle per context that Proposition 3.17 proved for tagged random oracles; the separation takes effect before any message byte is processed and, since BLAKE2 builds in keying and personalisation as parameters, costs less than HMAC. The deployed inventory spans both widths. On the BLAKE2b side, the key-expansion PRF PRF expand is BLAKE2b-512 personalised with Zcash_ExpandSeed (protocol specification §“Pseudo Random Functions”), evaluated on the spending key to derive Orchard’s key tree; the note-encryption KDF is personalised with Zcash_OrchardKDF (§“Orchard Key Derivation”) and the outgoing cipher key with Zcash_Orchardock (§“Pseudo Random Functions”)—all 16 -byte tags. On the BLAKE2s side, the nullifier PRF and fixed-base generators of Sapling—the shielded protocol preceding Orchard—use 8 -byte personalisations such as Zcash_nf and Zcash_PH (§“Pseudo Random Functions” and §“Pedersen Hash Function”).
Orchard derives the diversifiers behind its shielded addresses—one 11 -byte value per address, many addresses per spending key—by encrypting a sequential address index under a keyed bijection on the set of 11 -byte strings; an adversary who could invert the map, or distinguish it from a random permutation of that set, would link a wallet’s addresses to one another. The requirement is a block cipher whose “block” is an arbitrary finite set, as in encrypting a 16 -digit card number into a 16 -digit card number that legacy databases, field-length constraints, and checksum formats continue to accept. Format-preserving encryption (FPE) meets it.
Let X be a finite set, the format—for example
Since | X | need not be a power of two, a plain block cipher does not apply. FPE is necessarily deterministic, unlike the randomised encryption modes of the next section: the format X has no room to store a per-message random value. FPE therefore leaks equality of plaintexts, as any deterministic cipher must; this cost of preserving format with no expansion is acceptable for the tokenisation use cases FPE targets and immaterial for diversifier derivation, where each index is encrypted once.
Any format of the shape “strings of length ν over an alphabet of
radix ρ ” is in bijection with
Let
| L i = R i − 1, R i = L i − 1 ⊕ F i (R i − 1), i = 1, ..., r, |
and output (L r, R r) .
For any round functions
| R i − 1 = L i, L i − 1 = R i ⊕ F i (L i), i = r, ..., 1 . |
It suffices to show each round is invertible, the composition of
bijections being a bijection. The i -th round sends
Figure 8 draws one round and its inversion.
In FF1 the round functions derive from a PRF—AES iterated in cipher-block-chaining fashion, as specified below—so AES is evaluated only in the forward direction, in encryption and decryption alike.
Bijectivity holds for any round functions; pseudorandomness does not, but follows from PRF round functions and enough rounds.
Let the round functions
with
with
in each case with distinguishing advantage O (q 2 / 2 w) above the PRF advantage of the round functions.
We omit the proof; its outline accounts for the birthday term and the
round counts. One first replaces each PRF round function
by a truly random function, at the cost of r PRF advantage terms.
For three rounds one then shows that, unless two of the at most q
queries collide in an intermediate Feistel value—a birthday event of
probability O (q 2 / 2 w) —the middle round’s random function is
evaluated at distinct inputs, so it produces independent uniform
values that perfectly mask the relationship between input and output
halves, and the network’s answers are distributed exactly as a random
function’s—independent and uniform on { 0, 1 } 2 w . A
final application of the switching lemma
(Lemma 5.9), at a further cost of
Theorem 5.18 gives security only up to
The FF1 mode instantiates an unbalanced, modular, tweaked Feistel
network of ten rounds to build a PRP on Z / M Z with
Split. Set
Round function from a PRF. For each round
Modular Feistel step. Update the halves by the modular analogue of Definition 5.16:
| C = (A + y) mod m, A ← B, B ← C, |
where the modulus m alternates between
Output. After ten rounds, concatenate the final A and B and render the result back as a length- ν radix- ρ string.
Decryption runs the rounds in reverse, replacing modular addition by
modular subtraction,
For every key k and tweak T , the FF1 map
Each round is the map
Feistel networks are the standard route to FPE because they separate two obligations. Invertibility follows from the structure alone: Propositions 5.17 and 5.21 hold for any round function, including a constant one. The PRF, AES, supplies pseudorandomness: making E k, T look like a uniformly random permutation of X in the sense of Definition 5.15, per the Luby–Rackoff heuristic—Theorem 5.18 adapted, beyond what it literally proves, to the modular, multi-round, tweaked setting.
The published SP 800-38G requires
The single use of FF1 in Orchard is diversifier derivation: FF1-AES256
maps an address index to the 11 -byte diversifier embedded in a
shielded address, so that one spending key yields many mutually
unlinkable addresses. The deployed
instance (protocol specification
§“Pseudo Random
Permutations”) fixes radix