3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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, 2020 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, 2020 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, 2020 at 15:45

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2020 at 14:48
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.