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 keyed 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.

  • 6
    $\begingroup$ A fixed lookup table implements a particular permutation, but not a family of permutations. A block cipher implements the later. A fixed lookup table lacks a key. The question needs to carefully separate when PRF/PRP stands for a family (there is a key input), and when it stands for a particular function or permutation. $\endgroup$ – fgrieu Jul 1 '18 at 7:25
  • 1
    $\begingroup$ @fgrieu In this case it is an unkeyed permutation. A fixed lookup table could implement an Even-Mansour cipher (of very small block size and key size). $\endgroup$ – forest Jul 2 '18 at 7:27
  • $\begingroup$ ‘Unkeyed PRP’ is a contradiction in terms. You're mixing two categories: a distribution (perhaps uniform) on the space of permutations or functions, and a keyed family of functions. $\pi$ is presumably here a (uniform) random permutation—a random variable modeling uniform random distribution on permutations. An ideal cipher is a map from keys to independent uniform random permutations. Neither of these is a specific computable object; they're probability distributions. A PRP or a PRF, in contrast, is a specific computable object, which you might use with a uniform random key. $\endgroup$ – Squeamish Ossifrage Jul 4 '18 at 13:48
  • $\begingroup$ @SqueamishOssifrage Perhaps I used the terminology incorrectly. Here, $\pi$ is a fixed random permutation, equivalent to a block cipher with a fixed key (i.e. $\pi(m) = E_K(m)$ with a public $K$). $\endgroup$ – forest Jul 5 '18 at 2:42
  • $\begingroup$ @forest ‘Fixed random permutation’ doesn't make sense either except in the trivial sense that is the same as ‘probability distribution on one fixed permutation with probability 1’. We can talk about fixed permutations like Keccak-f[1600] or Gimli or $\operatorname{AES}_0$. We can also model a composition like $x \mapsto \pi(x + k) + k$ with $\pi$ modeled as a uniform random permutation. This is a random variable with a corresponding probability distribution on functions. We might consider its expected PRF advantage, integrated over all possible permutations $\pi$. $\endgroup$ – Squeamish Ossifrage Jul 5 '18 at 22:42

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.

  • $\begingroup$ Maybe you can, on average, make a good PRP out of this, if you specified enough details to matter. Can you elaborate a bit on this? $\endgroup$ – forest Jul 5 '18 at 23:30
  • $\begingroup$ @forest Not really—what I was getting at is that is that someone could, in principle, write down a lower bound on the expected PRP-distinguisher advantage in the random (permutation) oracle model, and it might be a pretty good expected advantage averaged over all permutations, but that's waaaaay more analysis that I'm keen to do right now. $\endgroup$ – Squeamish Ossifrage Jul 5 '18 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.