The Zcash ArboretumII Crypto Guide
Contents
PDF
Theme

5 Pseudorandom functions, block ciphers, and format-preserving encryption

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 ℓ form {0,1}ℓ, all finite strings form {0,1}∗, and |x| is the length of x; for a finite set S, the notation x←$S draws x uniformly from S, independently of everything else. Adversaries are PPT machines in the security parameter λ (§1.1), a negligible function is negl(λ) (recalled in §1.2), and every security notion below is a distinguishing game in the sense of Definition 1.15, scored by the difference

Adv⁢(𝒜)=|Pr⁡[𝒜⁢ outputs ⁢1⁢ in ⁢𝖤𝗑𝗉1]−Pr⁡[𝒜⁢ outputs ⁢1⁢ in ⁢𝖤𝗑𝗉0]|

between the two experiments the game distinguishes. Oracle access formalises the black box.

Definition 5.1 (Oracle access).

For a function f, the notation 𝒜f denotes an adversary granted oracle access to f: a black box to which 𝒜 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 λ.

5.1 Pseudorandom functions and permutations

Pseudorandomness is measured against an ideal object, the “truly random function”.

Definition 5.2 (Random function).

Let 𝖥𝗎𝗇𝖼(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 F←$𝖥𝗎𝗇𝖼(D,R), chosen uniformly at random. Equivalently, the values {F⁢(x)}x∈D are independent and uniformly distributed over R.

There are |R||D| functions in 𝖥𝗎𝗇𝖼(D,R), an infeasibly large set for the domains of interest: for D=R={0,1}128 the count is 2128⋅2128. Such a function has no description shorter than its truth table and cannot be stored; a pseudorandom function replaces it by a short key while preserving its observable behaviour. The ideal object is realised by lazy sampling, as for the random oracle of Definition 3.13: the oracle keeps a table, initially empty; on a fresh query x it samples F(x)←$R, 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 materialising only the queried points.

Definition 5.3 (Keyed function).

A keyed function is a deterministic, efficiently computable map

F:{0,1}λ×{0,1}ℓ⁢(λ)⟶{0,1}m⁢(λ),(k,x)⟼Fk⁢(x),

where the input length ℓ and output length m are polynomially bounded functions of the key length λ. Fixing the key k yields the function Fk:{0,1}ℓ⁢(λ)→{0,1}m⁢(λ).

Definition 5.4 (Pseudorandom function).

Let F be a keyed function. The distinguishing game 𝖯𝖱𝖥F𝒜(λ) runs as follows.

  1. 1.

    The challenger samples a bit b←${0,1}. If b=1 it samples k←${0,1}λ and sets 𝒪:=Fk; if b=0 it sets 𝒪:=R for R←$𝖥𝗎𝗇𝖼(ℓ(λ),m(λ)), realised by lazy sampling, where 𝖥𝗎𝗇𝖼(ℓ,m):=𝖥𝗎𝗇𝖼({0,1}ℓ,{0,1}m).

  2. 2.

    The adversary 𝒜(1λ), receiving the security parameter in unary to convey the parameter size, queries 𝒪 adaptively.

  3. 3.

    The adversary outputs a bit b′; the game outputs 1 iff b′=b.

The family F is a pseudorandom function (PRF) if for every PPT adversary 𝒜,

AdvFprf⁢(𝒜,λ):=|Prk←${0,1}λ⁡[𝒜Fk⁢(1λ)=1]−PrR←$𝖥𝗎𝗇𝖼⁢(ℓ⁢(λ),m⁢(λ))⁡[𝒜R⁢(1λ)=1]|∈negl⁡(λ).

The two probabilities are the adversary’s output distributions in the worlds b=1 and b=0, so this difference equals twice the bit-guessing advantage |Pr[𝖯𝖱𝖥F𝒜(λ)=1]−12| 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.

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 Fk takes at most 2λ distinct values in 𝖥𝗎𝗇𝖼(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.

Remark 5.5 (Necessity of adaptivity).

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.

Definition 5.6 (Keyed permutation).

A keyed function F:{0,1}λ×{0,1}ℓ→{0,1}ℓ with equal input and output length is a keyed permutation if for every key k the map Fk is a bijection of {0,1}ℓ, and both Fk and Fk−1 are efficiently computable given k. The set of all permutations of {0,1}ℓ is 𝖯𝖾𝗋𝗆(ℓ), of cardinality (2ℓ)!.

Definition 5.7 (Pseudorandom permutation).

Let F be a keyed permutation. The game 𝖯𝖱𝖯F𝒜(λ) is the game of Definition 5.4 with the ideal world replaced: for b=0 the challenger sets 𝒪:=P for P←$𝖯𝖾𝗋𝗆(ℓ), a uniformly random permutation. The family F is a pseudorandom permutation (PRP) if for every PPT adversary 𝒜,

AdvFprp⁢(𝒜,λ):=|Prk⁡[𝒜Fk⁢(1λ)=1]−PrP←$𝖯𝖾𝗋𝗆⁢(ℓ)⁡[𝒜P⁢(1λ)=1]|∈negl⁡(λ).
Definition 5.8 (Strong pseudorandom permutation).

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 𝒜,

AdvFsprp⁢(𝒜,λ):=|Prk⁡[𝒜Fk,Fk−1⁢(1λ)=1]−PrP←$𝖯𝖾𝗋𝗆⁢(ℓ)⁡[𝒜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 R∈𝖥𝗎𝗇𝖼(ℓ,ℓ) returns q independent uniform strings, which may collide, and a random permutation P∈𝖯𝖾𝗋𝗆(ℓ) returns q distinct uniform strings. Output collisions are the only statistical difference between the two, and the switching lemma bounds it.

Lemma 5.9 (PRP/PRF switching lemma).

Let ℓ≥1 and let 𝒜 be any adversary—even a computationally unbounded one—making at most q queries to its oracle. Then

|PrP←$𝖯𝖾𝗋𝗆⁢(ℓ)⁡[𝒜P=1]−PrR←$𝖥𝗎𝗇𝖼⁢(ℓ,ℓ)⁡[𝒜R=1]|≤q⁢(q−1)2ℓ+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 (q2)/2ℓ 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ℓ/2: the two advantages differ by at most q(q−1)/2ℓ+1. For AES, with ℓ=128, the switching term q2/2129 is negligible for any realistic query budget, so the FF1 construction of §5.4 uses AES—a permutation—as the PRF its round function requires.

5.2 Block ciphers and AES

Definition 5.10 (Block cipher).

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 D=E−1 satisfying Dk(Ek(x))=x for all k,x. Here Ek is encryption and Dk decryption under key k. The security goal is that E be a strong pseudorandom permutation (Definition 5.8).

The asymptotic PRP definition concerns a family indexed by λ; a block cipher fixes b and κ—b=128 and κ∈{128,192,256} for AES—and so offers concrete security in the style of Definition 1.31: an explicit function of the adversary’s resources bounds the advantage of the best known attacks.

Definition 5.11 (Concrete (t,q,ε)-security).

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 AdvEprp(𝒜)≤ε; analogously for SPRP and PRF security.

Construction 5.12 (AES).

The Rijndael cipher of Daemen and Rijmen, standardised as AES in FIPS 197, has block length b=128 bits and key lengths κ∈{128,192,256}, with Nr∈{10,12,14} rounds respectively. Structurally it is a substitution–permutation network (SPN): the 128-bit state, viewed as a 4×4 array of bytes—elements of 𝔽28—is first whitened by an initial round-key XOR, then passes through Nr rounds built from four layers:

  1. 1.

    SubBytes, a nonlinear byte substitution—the S-box—built on field inversion a↦a−1 in 𝔽28 (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;

  2. 2.

    ShiftRows, a transposition of bytes within the array;

  3. 3.

    MixColumns, an invertible column-wise linear mix; and

  4. 4.

    AddRoundKey, the XOR of a 128-bit round key that a key schedule expands from k.

The first Nr−1 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 Ek is a permutation as Definition 5.10 requires, and decryption applies the inverses in reverse order.

Remark 5.13 (Confusion, diffusion, and the status of AES security).

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.

5.3 PRFs from hash functions: length extension and keyed BLAKE2

Hash functions are a second source of PRFs. The naive keying of a hash H by prepending the key,

Fk⁢(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

HMACk(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 q2/2ℓ 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 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

Fk⁢(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.

Remark 5.14 (Zcash’s use of keyed and personalised BLAKE2).

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 𝖯𝖱𝖥𝖾𝗑𝗉𝖺𝗇𝖽 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”).

5.4 Format-preserving encryption and FF1

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.

Definition 5.15 (Format-preserving encryption).

Let 𝒳 be a finite set, the format—for example 𝒳={0,1,…,9}16, the 16-digit strings. A format-preserving encryption scheme on 𝒳 is a keyed permutation ℰ:{0,1}κ×𝒳→𝒳 such that for every key k the map ℰk:𝒳→𝒳 is a bijection with efficiently computable inverse 𝒟k. Security requires ℰ to be a (strong) pseudorandom permutation on 𝒳—Definition 5.7 with 𝖯𝖾𝗋𝗆(𝒳) in place of 𝖯𝖾𝗋𝗆({0,1}ℓ): no efficient adversary distinguishes ℰk from a uniformly random permutation of 𝒳, even with access to the inverse.

Since |𝒳| 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 𝒳 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 {0,1,…,ρν−1} by reading the string as a base-ρ numeral, so it suffices to build a keyed pseudorandom permutation of ℤ/Mℤ for an arbitrary modulus M=ρν. The FF1 construction below splits M=a⋅b into two factors of nearly equal size and runs, with halves in ℤ/aℤ and ℤ/bℤ, a Feistel network, which builds a permutation from round functions that need not be invertible.

Definition 5.16 (Balanced Feistel network).

Let F1,…,Fr:{0,1}w→{0,1}w be arbitrary round functions. The r-round Feistel network Ψ[F1,…,Fr] is the map on {0,1}2⁢w defined as follows: write the input as (L0,R0) with L0,R0∈{0,1}w, iterate

Li=Ri−1,Ri=Li−1⊕Fi⁢(Ri−1),i=1,…,r,

and output (Lr,Rr).

Proposition 5.17 (Feistel is a bijection regardless of the round functions).

For any round functions F1,…,Fr—injective or not—the map Ψ[F1,…,Fr] is a bijection of {0,1}2⁢w, inverted by running the rounds backwards:

Ri−1=Li,Li−1=Ri⊕Fi⁢(Li),i=r,…,1.
Proof.

It suffices to show each round is invertible, the composition of bijections being a bijection. The i-th round sends (Li−1,Ri−1)↦(Ri−1,Li−1⊕Fi(Ri−1)). Given the output (Li,Ri), one recovers Ri−1=Li directly, and then Li−1=Ri⊕Fi(Ri−1)=Ri⊕Fi(Li), using that XOR is its own inverse. The recovery uses only forward evaluations of Fi—at no point is an inverse of the round function required, and this permits a permutation to be built from a PRF that need not be invertible. The displayed backward recursion is exactly this inversion applied round by round. □

Figure 8 draws one round and its inversion.

Refer to caption
Figure 8: One round of the balanced Feistel network of Definition 5.16 (left) and its inversion (right). Forward, Ri−1 (amber) passes unchanged to Li and also enters Fi, whose output is XORed into Li−1 (blue) to give Ri; the rails then cross. The right panel is the same wiring read from bottom to top, the decryption direction: Li returns to the right rail as Ri−1 and enters Fi, and XORing its output into Ri recovers Li−1 (Proposition 5.17). In both directions Fi is evaluated forward, so it need not be invertible.

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.

Theorem 5.18 (Luby–Rackoff).

Let the round functions F1,…,Fr be independent PRFs on {0,1}w. Against an adversary making q queries, the Feistel network Ψ is:

  1. 1.

    with r=3 rounds, a pseudorandom permutation (forward queries only); and

  2. 2.

    with r=4 rounds, a strong pseudorandom permutation (forward and inverse queries);

in each case with distinguishing advantage O(q2/2w) 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(q2/2w)—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 q(q−1)/22⁢w+1, carries the comparison from the random function to the random permutation; the term is absorbed by the same O(q2/2w) 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.

Remark 5.19 (Why FF1 uses ten rounds rather than four).

Theorem 5.18 gives security only up to q≈2w/2 queries, and in the FPE setting w is small—one half of a 16-digit number—so the birthday bound q2/2w is weak. The standardised FF1 therefore prescribes ten rounds rather than the minimal four, as a security margin against the stronger attacks known for small-domain Feistel networks, which can sometimes beat the generic birthday bound. The round count is specified—NIST SP 800-38G fixes ten rounds—while a security proof matching the margin is an open problem: the existing analysis (Luby–Rackoff and its small-domain refinements) does not certify the full strength the margin is intended to provide. Invertibility does not depend on the round count (Proposition 5.17).

Construction 5.20 (The FF1 mode of NIST SP 800-38G).

The FF1 mode instantiates an unbalanced, modular, tweaked Feistel network of ten rounds to build a PRP on ℤ/Mℤ with M=ρν, the radix-ρ numeral reading of a length-ν string. It supports a tweak T: a non-secret string that selects, in effect, one permutation from a family indexed by T, so that the same key encrypts the same plaintext differently under different tweaks—useful for binding a token to its context. Its operation:

  1. 1.

    Split. Set u=⌊ν/2⌋ and v=ν−u. Split the plaintext numeral string X into a left part A of u symbols and a right part B of v symbols, with integer values in {0,…,ρu−1} and {0,…,ρv−1} respectively. The two halves live in the moduli a=ρu and b=ρv; the network is unbalanced when ν is odd.

  2. 2.

    Round function from a PRF. For each round i=0,1,…,9, assemble a byte string Q encoding the tweak T, the round index i, and the current right half B; prepend a fixed parameter block P encoding the radix, the lengths, and the tweak length; and apply PRF(P∥Q), where PRF is AES in CBC-MAC mode: set Y0=0128, iterate Yj=AESk(Yj−1⊕Xj) over the 16-byte blocks Xj of P∥Q, and output the final block Ym (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 P 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 y.

  3. 3.

    Modular Feistel step. Update the halves by the modular analogue of Definition 5.16:

    C=(A+y)modm,A←B,B←C,

    where the modulus m alternates between a=ρu and b=ρv with the parity of the round, so that the sum lands in the correct half’s domain; modular addition replaces XOR.

  4. 4.

    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, A←(C−y)modm, exactly mirroring the backward recursion of Proposition 5.17. In step 2 the standard sizes the expanded digest at least four bytes beyond what the larger half requires, so the integer y ranges over at least 232 multiples of the modulus, and the bias of the reduction ymodm away from uniform is bounded by the modular-reduction bias of the Math Guide (§“Uniform sampling and the bias of modular reduction”) at below 2−33 per round.

Proposition 5.21 (FF1 is a keyed bijection on 𝒳).

For every key k and tweak T, the FF1 map ℰk,T:𝒳→𝒳 is a bijection of the format set 𝒳, and 𝒟k,T is its two-sided inverse.

Proof.

Each round is the map (A,B)↦(B,(A+y)modm), where y=y(i,T,B) depends only on the round index, the tweak, and the right half B—not on A. Fix B, i, and T; then y is a constant and A↦(A+y)modm is a translation of ℤ/mℤ, hence a bijection, inverted by subtracting the same constant. The full round is therefore invertible: from the output (B,C) recover B directly, recompute y=y(i,T,B) by a forward PRF evaluation, and set A=(C−y)modm. Each even-indexed round is a bijection of ℤ/aℤ×ℤ/bℤ onto ℤ/bℤ×ℤ/aℤ 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 ℤ/aℤ×ℤ/bℤ. The numeral map (A,B)↦A⋅b+B identifies ℤ/aℤ×ℤ/bℤ with ℤ/Mℤ as a bijection of sets only, not of groups: the factors satisfy gcd(a,b)=ρmin⁡(u,v)>1, so the Chinese remainder theorem does not apply, and only bijectivity is used. Transporting through this map and the numeral bijection 𝒳≅ℤ/Mℤ, the composition ℰk,T is a bijection of 𝒳. Running the rounds backwards with subtraction inverts it on both sides, so 𝒟k,T=ℰk,T−1. □

Remark 5.22 (Bijectivity from algebra, security from the PRF).

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 ℰk,T 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.

Remark 5.23 (The domain-size caveat, and the single Orchard use).

The published SP 800-38G requires ρν≥100 and recommends ρν≥106—its draft Revision 1 would make 106 mandatory—because for 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.

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 ρ=2, length ν=88, and the empty tweak, and reads the 11-byte index as a little-endian bit string, so the domain is the 288 strings of 88 bits, far above both thresholds. The address built on the diversifier, and the case for a keyed permutation rather than a hash in this role, are treated in a later volume of the series.