# Pseudorandom permutations on domains of arbitrary (i.e. not a power of 2) size

The Feistel cipher algorithm produces a pseudorandom permutation with domain size equal to $2^{2m}$ (for some $m \in \mathbb{Z}^+$). That is, a one-to-one function $\pi$ of the set $\{0, 1, 2, \dots, 2^{2m} - 1\}$ onto itself.

Furthermore, with so-called unbalanced Feistel ciphers, it may be possible (though I don't know this for certain) to produce pseudorandom permutations of the set $\{0, 1, 2, \dots, 2^m - 1\}$ onto itself.

Is there an algorithm (possibly a modification of one of the ones mentioned above) to produce a pseudorandom permutation $\pi$ of the set $\mathbb{m} = \{0, 1, 2,\dots, m - 1\}$ for an arbitrary $m \in \mathbb{Z}^+$?

(Actually, the domain of the function $\pi$ produced by the algorithm may be a proper superset of $\mathbb{m}$, as long as the restriction $\pi|_{\mathbb{m}}$ is a permutation of $\mathbb{m}$.)

## 1 Answer

Yes. This is called format-preserving encryption.

The most flexible algorithm is FFX, which uses a Feistel network with AES-based round-functions, but performs addition modulo $m$. For certain values of $m$, the range of the round function is extended in order to limit statistical biases to negligible values.

When $m$ is very small, this approach isn't that great because its provable security gaurantees start to vanish if the adversary can see around $\sqrt{m}$ queries. If this is a concern, you can look at slower but more secure algorithms like Sometimes-Recurse Shuffling.