# Compacting a substitution cipher key

In a substitution cipher, I recieve 3 bits and than I return another 3 bits. The key of this cipher could be a matrix represented as:

(0) 0 0 0 => 0 1 1

(1) 0 0 1 => 1 0 1

(2) 0 1 0 => 1 1 1

(3) 0 1 1 => 0 1 0

(4) 1 0 0 => 0 0 1

(5) 1 0 1 => 1 0 0

(6) 1 1 0 => 0 0 0

(7) 1 1 1 => 1 1 0


So, when we receive 000, the cipher will return 011.

When we receive 101, the cipher will return 100.

The key itself can be represented as a stream of 24 bits like this:

0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0


Is there a way to reduce the key to 15 bits?

I other words, can that matrix representation of 24 bits, could be represented with 15 bits?

• That's not a key, that's a permutation from ${\{0,1}\}^3$ to ${\{0,1\}}^3$. And it is identical to performing XOR with 1 for each bit, also known as a bit complement. – Maarten Bodewes May 24 '15 at 20:09
• Maarten Bodewes, my key example was unfortunate... I changed there to a random mapping – user24664 May 24 '15 at 20:18
• OK, now it is a random permutation from ${\{0,1\}}^3$ to ${\{0,1\}}^3$, helped you a bit with the edit. I presume any random permutation is allowed. – Maarten Bodewes May 24 '15 at 20:25

There are $8! = 40320$ permutations over 3 bits; 15 bits of key allows you to specify $2^{15} = 32768$ of them; hence any mapping of 15 bits will necessarily $40320-32768 = 7552$ of permutations unexpressable.