Indexing a random permutation

Question

I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$.

Something that comes very close to my goal is a block cipher, say AES. But block ciphers have fixed block size (e.g. 64, 128 bits), and I want something with parameterizable (and smaller) "block size" $\log_2 |X|$. I also don't need many characteristics of block ciphers (e.g. $k$ secrecy, etc.), only the permutation part.

Something else that is quite close is the Lehmer code. However, this takes into consideration all possible permutations $|X|!$, and would need the index (or "key") $k$ to be as large as $|X| \log_2 |X|$. I am happy with only $K << |X|!$ possible permutations (so long as $K$ is "big enough").

Answer 1

You can build a block cipher with any desired block size, using a method called "format preserving encryption". The block size doesn't have to be limited to 64 bits or 128 bits. This will provide a reasonable solution to your problem.

See Bijective algorithm(s) that can shuffle a range of numbers back and forth, Pseudo random, unqiue integer numbers in a given range, Invertible function that randomizes order, Efficiently generating a uniformly random list of unique integers in a range, Lazily computing a random permutation of the positive integers.

Answer 2

If you don't want to use $|X|\log|X|$ bits you have to specify which permutations you want. Since that's up to you, basically any reasonable method works. For example you can pick $F_k$ to be the $k$-th permutation in lexicographic order and just cut off $k$ whereever you want.