A non-cryptographic definition of a permutation is "2a: the act or process of changing the lineal order of an ordered set of objects. 2b: an ordered arrangement of a set of objects

The Wikipedia article on Random permutation states that "A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards."

An ideal block cipher is a pseudorandom permutation.

Shuffling a deck of identical cards would result in output indistinguishable from the input. Applying an ideal block cipher to an all-zero (or all-one) plaintext block would yield a random ciphertext block, not the same all-zero (or all-one) input block!

What's an easy-to-understand difference between a shuffle (equivalently a transposition cipher) and a permutation in the sense meant by cryptographers?

  • $\begingroup$ Looking to see if anyone has better/clearer/more intuitive answers. It's easy enough to state the difference using mathematical notation, but getting it across clearly without that seems a bit harder. $\endgroup$ – SAI Peregrinus Nov 6 '20 at 2:57
  • $\begingroup$ I do not understand the distinction you are trying to make. Could you try to clarify it some? This is likely complicated because a transposition has a well-defined mathematical meaning which appears to be distinct from what you mean (in particular, transpositions are permutations which interchange exactly two elements, so the subset of transpositions is a subset of the set of all permutations. The subgroup generated by these elements is the full permutation group though). $\endgroup$ – Mark Nov 6 '20 at 6:01
  • $\begingroup$ Swapped it to "transposition cipher" since that's the more precise term I was going for. $\endgroup$ – SAI Peregrinus Nov 6 '20 at 15:45

To continue your deck of cards analogy, the permutation is analogous to replacing each card in a set with one from a full deck. With a new full deck for each card.

If someone can understand that, then they can understand that each card represents 4 digits/etc and that the deck of cards is 10k/etc in size.

  • $\begingroup$ I'm accepting this because it's a good answer, and keeps the same analogy. Though there's the additional restriction that a permutation must be bijective, but that's easy enough to tack on. $\endgroup$ – SAI Peregrinus Nov 9 '20 at 14:48

A shuffle (or transposition function) re-arranges elements of the input. A permutation re-arranges the entire output domain.

For example, compare the following transposition function and pseudorandom permutation:
The transposition takes in a 4-digit number, and re-arranges the digits. 1234 might become 4213, but never 1692.
A pseudorandom permutation has a shuffled list of all possible 4-digit numbers, and an unshuffled list of all possible 4-digit numbers. It looks up the input number in the unshuffled list, finds the corresponding number in the shuffled list, and outputs that. 1234 might become 1692.


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.