3
$\begingroup$

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").

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.