# Why is a Feistel network bijective?

EDIT: Fixed for clarity of intention

I was reading "The FFX Mode of Operation for Format-Preserving Encryption" when I came across Figure 1 (see below). It's obvious why it's reversible (top-down then down-top) but it's not clear why it should strictly be bijective instead of not-injective or not-surjective? What rules out the possibilities of collisions or skips that make it strictly one-one in both directions?

For example: The round function (Fk) can be block cipher or hash based and we pick a subset of output bits into the next round. A collision at say, Fk(n,T,0), in round zero would then map two inputs at the top to a single input at the bottom. Why is that not an issue? Sorry if I'm missing something but it's been a long night and have missed my morning coffee.

Example Feistel network from FFX paper: ## 1 Answer

why it should strictly be bijective instead of injective or surjective?

Actually, it is injective and it is surjective; the term bijective just means that it satisfies both the properties of injectivity and surjectivity.

Injective does not mean that there is a 'skip' (that's "not surjective"); instead, it states that no two different inputs give the same output; that is, if $a \ne b$, then $F(a) \ne F(b)$. This follows immediately from the reversibility (invertibility) of the function; if we did have two different inputs that gave the same output, then we couldn't invert the output to get the input.

Similarly, surjective doesn't mean 'has collisions' (that's "not injective"), instead, it states that every output is possible, that is, for every $x$, there is an $a$ with $F(a)=x$. This can be shown by noting that the size of the input and the size of the output are the same, and that they are both finite. As each output has a unique input, then by the pigeon hole principle, every output is possible (because every input is possible).

The above conversation was about functions; now, FFX is a keyed function. What this means is that FFX, with a fixed key, is a bijective function (because it is both injective and surjective).

• The round function (Fk) can be block cipher or hash based and we pick a subset of output bits into the next round. A collision at say, Fk(n,T,0), in round zero would then map two inputs at the top to a single input at the bottom, right? – DeepSpace101 Jun 4 '15 at 17:33
• Ok, as soon as I edited my question it came to me, the different input (B0) continues to propagate down on the side ... need coffee! – DeepSpace101 Jun 4 '15 at 17:35