# Selecting bijective functions for permutations

How would one go about selecting an appropriate bijective function for introducing permutations into a cipher or hash?

For example, $f(x) = x+1 \space mod \space n$ is a bijective function, but isn't particularly good as a permutation, in that the outputs do not vary sufficiently when an input bit is changed.

The same applies to $f(X_i) = X_{\sigma(i)}$, where $\sigma(i) \equiv i+1\space mod\space |X|$, i.e. a circular shift.

If I understand it correctly, modular exponentiation can be bijective if you select appropriate parameters, but it's rather slow.

• In most cases we use pretty simple but very fast functions. If you have enough rounds of these it becomes exponentially complicated. For example xor, modular addition and rotation in an ARX cipher, or an sbox in AES. Jul 9, 2013 at 20:57
• @CodesInChaos Surely those first operations aren't sufficient? I understand the s-box somewhat, though from my understanding it's a transposition of smaller chunks rather than the entire block. Jul 9, 2013 at 21:02
• @Polynomial They are - look at Threefish for instance, an ARX cipher with simple permutations and no s-boxes. Even if those operations are simple, repeating them a sufficient number of times leads to high confusion and diffusion. And after all, modular exponentiation is a series of multiplications, which themselves are series of additions... of course this is an oversimplification, it takes a lot of work to make sure the way you're combining the operations leads to such behaviour. Jul 9, 2013 at 22:17
• I would also suggest taking a look at the permutation inside Keccak, it doesn't use any S-Boxes either... Jul 10, 2013 at 18:35