Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've noticed confusing definitions about permutation and substitution, preventing to make the difference.

A permutation changes the order of distincts elements of a set, but this can be writen as a function changing one element by another, exactly as a substitution.

So how can we distinguish exactly these two notions ?

This question is interesting since we have these two notions in block ciphers, substitution table with also permutation. The problem is that this table is used to replace one element by another, exactly like a permutation.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

As noted in this answer and this answer to another question, permutation is just a mathematical term for a function $\sigma:X{\rightarrow}X$ that maps a finite set $X$ onto itself, in such way that for each $y \in X$ there exists exactly one $x \in X$ such that $\sigma(x) = y$. This is also equivalent to how the term substitution is used in cryptography, so your question is indeed justified.

For instance, the term Pseudo Random Permutation denotes a function that might also have been described as a Pseudo Random Substitution (but never is).

As D.W. pointed out in a comment below, the terms P-boxes (permutation boxes) and S-boxes (substitution boxes) have a specific meaning in block cipher design. Suppose you have a P-box and a S-box that both map a bit-string of length $n$ to another bit-string of length $n$. In such case the P-box can be expressed as a function $\sigma:[0..n-1]\rightarrow[0..n-1]$ that maps one index in the bit string to another, while the S-box, simply put, does more. This means that there are only $n! = \Pi_{i=1}^ni$ different P-boxes that map one bit string of length $n$ to another, while there are $2^n!-n!$ different S-boxes that map any bit string of length $n$ to another, without being a P-box and without mapping two different inputs to the same output.

Using the term Permutation in the specific meaning described in the above paragraph is unambiguous within the field of block cipher design. However, I would recommend using the term P-box, which, to the best of my knowledge, is never used in a meaning that differs from above.

Why? Well, for instance, a block cipher designer who hypothetically decides to incorporate e.g. the RC4 key schedule for setting up the S-boxes used in a block cipher, would be technically correct to refer to the operation that sets up those S-Box as a "permutation" (because one property of such a S-box might be best understood by looking at the setup in terms of permutation decomposition). The result would clearly not be a P-box, though.

Consequently, the best answer is probably that the distinction must be clear from definitions made in the context where the terms appear. When in doubt, avoid terms that might cause confusion.

share|improve this answer
    
Thank you for your answer. –  Dingo13 May 31 '13 at 7:36
    
Thank you Henrick, now it's completely clear. –  Dingo13 Jun 3 '13 at 6:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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