Using a PRP $\pi: \{0,1\}^{16} \to \{0,1\}^{16}$ to construct an ideal cipher

Question

Say we have an ideal 16-bit PRP. Since it appears that a permutation with a small domain can be used to turn it into a PRF, which can then be used in a Feistel network. On the surface, it makes it look like this means a trivial random permutation implemented using nothing more than a lookup table could then be used to create an ideal cipher with an arbitrary block and key size, which is obviously not the case. There must be something I am missing.

The way I see it:

• A small, random permutation can be implemented in practice using a lookup table.

• A random permutation can be used to implement a PRP, e.g. $C = \pi(P \oplus K) \oplus K$.

• A PRP with a small domain can be used to construct a secure PRF.

• A secure PRF in a Feistel network can be used to create a secure block cipher.

A random permutation with a small domain can be implemented easily using a lookup table. Were I any more naïve, I would have proclaimed that I had just discovered an information theoretic secure cipher that fits the ideal cipher model, but obviously that is not the case. Why is this?

This is not a cryptosystem review question in disguise. I am simply curious to know the reason why an ideal but small PRP cannot be used to construct a cipher that fits the ideal cipher model.

Answer 1

There are $2^{16}!$ distinct permutations of the 16-bit strings $\{0,1\}^{16}$. For any fixed Feistel structure built out of one of these as you suggest, there are still only $2^{16}!$ possible outcomes.

There are $2^{128}!$ distinct permutations of the 128-bit strings $\{0,1\}^{128}$. In an ideal cipher, for any fixed key $k$, $E_k$ is an independent uniform random permutation: each possible permutation has probability $1/2^{128}!$ of being $E_k$.

But in your construction, there are at least $2^{128}! - 2^{16}!$ permutations that $E_k$ cannot be. (There may be more because conceivably some pairs of permutations may collide under the Feistel structure, pending further analysis to rule that out.) So no matter what Feistel structure you choose, or non-Feistel composition of the permutation, you cannot get an ideal 128-bit block cipher out of a random 16-bit permutation.

What about a pseudorandom permutation family? Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter.

Table lookups are, indeed, a common design element in cryptographic primitives, including the venerable DES. You can view AES as a composition of table lookups and xor, but as the rest of the paper demonstrates this implementation strategy will lead you into trouble, which is why alternative designs like Serpent and newer designs like Salsa20 don't even tempt implementors into using secret-dependent table lookups.

Further, to make a thing that can be computed with, rather than a probability distribution that can be studied, you need to choose particular tables—and as Don Coppersmith and his team at IBM learned in 1974, the choice of tables can be tricky.