The adversary of this section sits before a black box. She may submit any input she likes and read off the answer; she may let each query depend on everything the box has said so far; and when she has asked all she cares to ask, she must announce a single bit: does a short secret key drive the box, or blind chance? If no efficient strategy tells the difference, then bits of key have bought a perfect counterfeit of an object too large to exist in the world—a uniformly random function—and everything downstream that needs random-looking values on demand can draw them from that key. If she can tell, forgery follows at once. Key a Merkle–Damgård hash by naive concatenation and she extends an authentication tag she was shown onto a message nobody authenticated, without ever learning the key. Derive the diversifiers behind Orchard’s shielded addresses by any map she can predict or invert, and she links every address of one wallet to its siblings. One adversary—the oracle distinguisher—thus carries the whole section, and every definition in it is the same distinguishing game at a different strength: pseudorandom functions against random functions, pseudorandom permutations against random permutations, strong pseudorandom permutations against a two-sided oracle. The switching lemma prices the substitution of one ideal object for the other; AES supplies the deployed permutation; keyed BLAKE2 supplies the PRFs this section inventories; and format-preserving encryption closes the section by manufacturing, from a PRF that is not invertible, the keyed bijection on an 11-byte format that Orchard’s address derivation demands.
Notation is that of the provable-security model. Strings of length form , all finite strings form , and is the length of ; for a finite set , the notation draws uniformly from , independently of everything else. Adversaries are PPT machines in the security parameter (§1.1), a negligible function is (recalled in §1.2), and every security notion below is a distinguishing game in the sense of Definition 1.15, scored by the difference
between the two experiments the game distinguishes. One device remains to be formalised: the black box itself.
For a function , the notation denotes an adversary granted oracle access to : a black box to which may submit inputs of its choice, receiving in a single computation step, and from which it learns nothing about 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, which must come first: the “truly random function” has to be made precise before anything can be said to imitate it.
Let denote the set of all functions from a finite set to a finite set . A random function from to is an element , chosen uniformly at random. Equivalently, the values are independent and uniformly distributed over .
There are functions in , an astronomically large set for the domains of interest: for the count is . No such function can be stored or transmitted—its truth table is the only description it has, and the table does not fit in the universe. The essential property of a pseudorandom function is that it replaces this object by a short key while preserving its observable behaviour. The clean mental model of the ideal object is lazy sampling, exactly as for the random oracle of Definition 3.13: the oracle keeps a table, initially empty; on a fresh query it samples , records the pair, and returns it; on a repeated query it returns the recorded value. This produces exactly the distribution of Definition 5.2 while only ever materialising the points actually queried.
A keyed function is a deterministic, efficiently computable map
where the input length and output length are polynomially bounded functions of the key length . Fixing the key yields the function .
Let be a keyed function. The distinguishing game runs as follows.
The challenger samples a bit . If it samples and sets ; if it sets for , realised by lazy sampling, where .
The adversary , receiving the security parameter in unary to convey the parameter size, queries adaptively.
The adversary outputs a bit ; the game outputs iff .
The family is a pseudorandom function (PRF) if for every PPT adversary ,
The two probabilities are the adversary’s output distributions in the worlds and , so this difference equals twice the bit-guessing advantage of Definition 1.15; the factor of two is immaterial to negligibility, and the difference form is the one every bound below is stated in.
Stated informally: an adversary handed a black box that is either for a secret random key or a freshly sampled truly random function, and allowed to query it adaptively, cannot tell which it holds. Two features of the definition carry the weight. First, the algorithm defining is public; only the sampled key is hidden. The adversary obtains oracle access to the resulting keyed instance through Definition 5.1—never the key, only its input–output behaviour. Second, the comparison object is the gigantic, unstorable random function; the PRF compresses it into bits while remaining indistinguishable to every efficient observer.
That last qualifier is not removable: pseudorandomness is an inherently computational notion. Information theory cannot afford the trade. As ranges over its values, the keyed function takes at most distinct values in —a vanishing fraction of all functions—so the two distributions of Definition 5.4 are statistically almost as far apart as distributions can be, and an unbounded adversary could in principle distinguish them. Security holds only against computationally bounded distinguishers, in precisely the manner of the PRG separation in the proof of Proposition 1.10.
The adversary chooses its queries; it need not commit to them in advance, and later queries may depend on earlier answers. This adaptive access is the strongest reasonable model and the one downstream constructions rely on. A weaker non-adaptive definition, in which the adversary fixes all queries before seeing any answer, is genuinely weaker—families exist that pass every non-adaptive test yet fall to an adaptive distinguisher—and is insufficient for many applications.
A block cipher is not merely a keyed function but a keyed permutation: each key must yield an invertible map, or decryption would be impossible. The relevant ideal object is therefore a random permutation.
A keyed function with equal input and output length is a keyed permutation if for every key the map is a bijection of , and both and are efficiently computable given . The set of all permutations of is , of cardinality .
Let be a keyed permutation. The game is the game of Definition 5.4 with the ideal world replaced: for the challenger sets for , a uniformly random permutation. The family is a pseudorandom permutation (PRP) if for every PPT adversary ,
A keyed permutation 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 ,
The distinction between a PRP and an SPRP is exactly the availability of a decryption oracle. A block cipher deployed where the attacker can obtain decryptions of chosen ciphertexts must be an SPRP; this is the natural security target for a block cipher, and the one the next subsection adopts.
From the outside, the two ideal objects are nearly the same thing. Query a length-preserving oracle on distinct inputs. If the oracle is a random function , the answers are independent uniform strings, and output collisions occur. If the oracle is a random permutation , the answers are distinct uniform strings, and no collision can occur. This is the only statistical difference visible to any observer, and it is the entire content of the switching lemma.
Let and let be any adversary—even a computationally unbounded one—making at most queries to its oracle. Then
We use the lemma as a statement only. Its proof is a standard game-hopping argument (Remark 1.18) bounding the probability of the single distinguishing event just identified—an output collision among the answers—and the bound is the birthday-type count familiar from Lemma 3.11, whose underlying calculation is the Math Guide’s (§“The union bound and a birthday calculation”).
The consequence is a licence: a secure PRP on a large domain is also a secure PRF whenever the number of queries stays well below the birthday bound , because the adversary’s total advantage against the function world exceeds its advantage against the permutation world by at most . For AES, with , the switching term is negligible for any realistic query budget. This is the licence by which the FF1 construction of §5.4 treats AES—a permutation—as the PRF its round function requires.
A block cipher with block length and key length is a keyed permutation
together with its inverse satisfying for all . Here is encryption and decryption under key . The security goal is that be a strong pseudorandom permutation (Definition 5.8).
A block cipher is a concrete, fast, fixed-parameter instantiation of the SPRP abstraction, and the fixing of parameters changes the language of its security claims. The asymptotic PRP definition speaks of a family indexed by ; a real block cipher fixes and once and for all— and for AES—and offers concrete security in the resource-explicit style of Definition 1.31: an explicit function of the adversary’s resources bounds the advantage of the best known attacks.
A block cipher is a -secure PRP if every adversary running in time at most and making at most oracle queries has ; analogously for SPRP and PRF security.
The Rijndael cipher of Daemen and Rijmen, standardised as AES in FIPS 197, has block length bits and key lengths , with rounds respectively. Structurally it is a substitution–permutation network (SPN): the -bit state, viewed as a array of bytes—elements of —is first whitened by an initial round-key XOR, then passes through rounds built from four layers:
SubBytes, a nonlinear byte substitution—the S-box—built on field inversion in (composed with a fixed affine map), chosen so that every input difference maps to any given output difference with only small probability, and every linear approximation of it holds with probability close to one half;
ShiftRows, a transposition of bytes within the array;
MixColumns, an invertible column-wise linear mix; and
AddRoundKey, the XOR of a -bit round key that a key schedule expands from .
The first rounds compose all four layers in this order; the final round omits MixColumns. The two permutation layers together guarantee that after two rounds every output byte depends on every input byte. Each layer—the initial whitening included—is individually invertible, so is a permutation as Definition 5.10 requires, and decryption applies the inverses in reverse order.
The SPN design is the modern embodiment of 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 is what 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 theorem downstream therefore takes “ is a PRP/SPRP” as an assumption and reasons from it—the same epistemic footing on which Remark 1.29 placed the concrete hash functions.
Block ciphers are one source of PRFs; cryptographic hash functions are another, often more convenient one, being unkeyed and ubiquitous. Here the oracle distinguisher does not merely distinguish—she forges. The naive keying of a hash by prepending the key,
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 and alone, the adversary computes for a suffix of her choosing, without knowing . The reason is structural: a Merkle–Damgård digest is exactly the internal chaining state after absorbing , so the published output is a resumable snapshot of the iteration, and the attacker simply continues absorbing blocks from where the honest computation stopped. 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 surrenders a valid tag on , a message the key holder never authenticated.
The classical repair is HMAC, the nested double call
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 in the chaining-state length ; 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 in passing under “Key-derivation functions” in the next section. This summary is all we need, because the shielded protocol uses HMAC nowhere: its hash of choice admits direct keying.
Modern 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—do not suffer length extension and so admit a far simpler 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.) One simply writes
and obtains a PRF directly—no nested double call. No length-extension attack remains to repair: 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 pervasively, exploiting two parameters of the BLAKE2 design: the key, for PRF and MAC use as above, and the personalisation string, a domain-separation tag baked into the initial state— bytes for BLAKE2b, bytes for BLAKE2s. Personalisation makes the same input hashed for two purposes—nullifier derivation versus note-commitment derivation, say—yield independent-looking outputs, so each use site is effectively an independent PRF: the practical realisation of the independent-oracle-per-context idiom that Proposition 3.17 proved for tagged random oracles, obtained here before a single message byte is processed and cheaper and cleaner than HMAC, because BLAKE2 provides keying and domain separation as first-class features. The deployed inventory spans both widths. On the BLAKE2b side, the key-expansion PRF 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 -byte tags. On the BLAKE2s side, the nullifier PRF and fixed-base generators of Sapling—the shielded protocol preceding Orchard—use -byte personalisations such as Zcash_nf and Zcash_PH (§“Pseudo Random Functions” and §“Pedersen Hash Function”).
All constructions so far operate on bit strings of a length the cipher’s block size dictates. The deployed need that closes this section does not. Orchard derives the diversifiers behind its shielded addresses—one -byte value per address, many addresses per spending key—by encrypting a sequential address index with a keyed bijection on the set of -byte strings, so that the published diversifiers of one wallet look like unrelated random values rather than the consecutive integers they conceal. An adversary who could invert the map, or merely distinguish it from a random permutation of the format, would link a wallet’s addresses to one another. What is needed is precisely a block cipher whose “block” is an exotic finite set; the classical commercial need—encrypting a -digit card number into a -digit card number so that legacy databases, field-length constraints, and checksum formats continue to accept it—is the same problem. This is the problem format-preserving encryption (FPE) solves.
Let be a finite set, the format—for example , the -digit strings. A format-preserving encryption scheme on is a keyed permutation such that for every key the map is a bijection with efficiently computable inverse . Security requires to be a (strong) pseudorandom permutation on —Definition 5.7 with in place of : no efficient adversary distinguishes from a uniformly random permutation of , even with access to the inverse.
The defining feature is that the domain is arbitrary—in particular need not be a power of two, so a plain block cipher does not apply. What is required is a keyed pseudorandom bijection on a set whose size is, say, . Determinism is forced, and it separates FPE from the randomised encryption modes of the next section: the format has no room to store a per-message random value, so FPE is the deterministic, format-preserving analogue of a block cipher on the alphabet of . It necessarily leaks equality of plaintexts, as any deterministic cipher must; this is the unavoidable cost of preserving format with no expansion, and it is acceptable for the tokenisation use cases FPE targets—and immaterial for diversifier derivation, where each index is encrypted once.
Formats reduce to integers. Any format of the shape “strings of length over an alphabet of radix ” is in bijection with by reading the string as a base- numeral, so it suffices to build a keyed pseudorandom permutation of for an arbitrary modulus . The FF1 construction below splits into two factors of nearly equal size and runs a Feistel network whose two halves live in and . The Feistel network is the structural device that turns a round function—not necessarily invertible—into a permutation; we present the classical bitwise case first, then the modular generalisation FF1 uses.
Let be arbitrary round functions. The -round Feistel network is the map on defined as follows: write the input as with , iterate
and output .
For any round functions —injective or not—the map is a bijection of , inverted by running the rounds backwards:
It suffices to show each round is invertible, the composition of bijections being a bijection. The -th round sends . Given the output , one recovers directly, and then , using that XOR is its own inverse. The recovery uses only forward evaluations of —at no point is an inverse of the round function required, which is the crucial point permitting a permutation to be built out of a one-way-ish PRF. The displayed backward recursion is exactly this inversion applied round by round. □
This proposition is the structural heart of format-preserving encryption: it manufactures a keyed bijection from a keyed function that is not itself a bijection. In FF1 the round functions derive from a PRF—AES iterated in cipher-block-chaining fashion, as the construction below specifies—so the network is invertible without ever inverting the PRF: AES is only ever evaluated in the forward direction, in encryption and decryption alike.
Bijectivity is free; pseudorandomness is not. The Luby–Rackoff theorem is the classical statement that enough Feistel rounds over a PRF yield a pseudorandom permutation.
Let the round functions be independent PRFs on . Against an adversary making queries, the Feistel network is:
with rounds, a pseudorandom permutation (forward queries only); and
with rounds, a strong pseudorandom permutation (forward and inverse queries);
in each case with distinguishing advantage above the PRF advantage of the round functions.
We use the theorem as a statement, without proof, but the shape of the argument is worth recording, because it explains both the birthday term and the round counts. One first replaces each PRF round function by a truly random function, at the cost of PRF advantage terms. For three rounds one then shows that, unless two of the at most queries collide in an intermediate Feistel value—a birthday event of probability —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 . A final application of the switching lemma (Lemma 5.9), at a further cost of , carries the comparison from the random function to the random permutation; the term is absorbed by the same bound. The fourth round adds the symmetry needed to resist inverse queries as well, upgrading PRP to SPRP. The full argument is a transcript analysis bounding the probability of any internal collision; the leftover term is the stated birthday bound.
Theorem 5.18 gives security only up to queries, and in the FPE setting is tiny—one half of a -digit number—so the birthday bound is weak. The standardised FF1 therefore prescribes ten rounds rather than the minimal four, as a security margin against the more powerful attacks known for small-domain Feistel networks, which can sometimes beat the generic birthday bound. The classification of this design claim is worth making explicit: the round count itself is specified—NIST SP 800-38G fixes ten rounds—while a security proof matching the margin is an open problem; the analysis that exists (Luby–Rackoff and its small-domain refinements) does not certify the full strength the margin is hoped to buy. What the round count does not affect is invertibility, which Proposition 5.17 guarantees for any round count and any round function.
The FF1 mode instantiates an unbalanced, modular, tweaked Feistel network of ten rounds to build a PRP on with , the radix- numeral reading of a length- string. It supports a tweak : a non-secret string that selects, in effect, one permutation from a family indexed by , so that the same key encrypts the same plaintext differently under different tweaks—useful for binding a token to its context. Its operation:
Split. Set and . Split the plaintext numeral string into a left part of symbols and a right part of symbols, with integer values in and respectively. The two halves live in the moduli and ; the network is unbalanced when is odd.
Round function from a PRF. For each round , assemble a byte string encoding the tweak , the round index , and the current right half ; prepend a fixed parameter block encoding the radix, the lengths, and the tweak length; and apply , where is AES in CBC-MAC mode: set , iterate over the -byte blocks of , and output the final block (SP 800-38G, Algorithm 6). The iteration chains AES through an evolving state exactly as the Merkle–Damgård iteration of §5.3 chains a compression function; emitting the final state is safe here because the PRF’s inputs form a prefix-free set: the leading block encodes the lengths of everything that follows, so two distinct inputs either differ already in their first block or agree on all lengths, and in neither case is one a proper prefix of the other. Prefix-free inputs are precisely the setting in which plain CBC-MAC is proved to be a PRF (a result of Petrank and Rackoff), and no length-extension query can arise. Further AES calls then expand the result to a long enough digest, which is read as an integer .
Modular Feistel step. Update the halves by the modular analogue of Definition 5.16:
where the modulus alternates between and with the parity of the round, so that the sum lands in the correct half’s domain; modular addition replaces XOR.
Output. After ten rounds, concatenate the final and and render the result back as a length- radix- string.
Decryption runs the rounds in reverse, replacing modular addition by modular subtraction, , exactly mirroring the backward recursion of Proposition 5.17. One quantitative detail of step 2 deserves note: the standard sizes the expanded digest at least four bytes beyond what the larger half requires, so the integer ranges over at least multiples of the modulus, and the bias of the reduction away from uniform is bounded by the modular-reduction bias of the Math Guide (§“Uniform sampling and the bias of modular reduction”) at below per round.
For every key and tweak , the FF1 map is a bijection of the format set , and is its two-sided inverse.
Each round is the map , where depends only on the round index, the tweak, and the right half —not on . Fix , , and ; then is a constant and is a translation of , hence a bijection, inverted by subtracting the same constant. The full round is therefore invertible: from the output recover directly, recompute by a forward PRF evaluation, and set . Each even-indexed round is a bijection of onto and each odd-indexed round a bijection back, the two products coinciding when is even; the composition of the ten rounds, an even number, is a bijection of . The numeral map identifies with as a bijection of sets only, not of groups: the factors satisfy , so the Chinese remainder theorem does not apply, and only bijectivity is used. Transporting through this map and the numeral bijection , the composition is a bijection of . Running the rounds backward with subtraction inverts it on both sides, so . □
The construction separates its two obligations cleanly, and the separation is why Feistel is the standard route to FPE. Invertibility comes for free from the structure: Propositions 5.17 and 5.21 hold for any round function whatsoever, including a broken or constant one. The PRF—AES—is responsible not for invertibility but for pseudorandomness: making look like a uniformly random permutation of 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.
Two facts complete the picture, one cautionary and one deployed.
The domain-size caveat is real. The published SP 800-38G requires and recommends —its draft Revision 1 would make mandatory—because for very small domains an attacker can recover or distinguish the keyed permutation by exhaustively cataloguing input–output pairs, and known message-recovery attacks on small-domain FPE (Bellare–Hoang–Tessaro and successors) erode the security margin. For the moderately large domains FPE is meant for, and with its ten rounds, FF1 is the NIST-standardised, AES-backed realisation of a keyed pseudorandom bijection on an arbitrary finite format.
The single use of FF1 in Orchard is the diversifier derivation with which this subsection opened: FF1-AES256 maps an address index to the -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 , length , and the empty tweak, and reads the -byte index as a little-endian bit string, so the domain is the strings of bits—comfortably beyond the caveat above. The address built on the diversifier, and the case for a keyed permutation rather than a hash in this role, are the business of the Ironwood Guide (§“Diversified addresses”).
The toolbox has gained its keyed compartment: one distinguishing game at three strengths, a standard permutation conjectured to win it, a natively keyed hash that turns domain-separated digests into independent PRFs, and a Feistel construction that bends a PRF into a bijection on any finite format. The next section spends these tools on the channel itself: symmetric encryption, authentication, and the authenticated-encryption composition that carries every shielded note, each built by running a PRF in a mode that converts its indistinguishability into secrecy or integrity.