I'm trying to answer a question on cryptography.
Basically, inputs and outputs (so plaintexts and ciphertexts) are from the set (say) $\{0, 1\}^{100}$. The encryption function takes inputs and splits them up into 50 bits each, messes around with them, then reassembles them into the 100-bit output. The key (that is used for encrypting) is from a larger set, say $\{0, 1 \}^{204}$, and the cryptosystem is linear in the key (in other words, the only action the key really does is $\oplus$, obviously with subections of the key of size 50). The only other weird thing about the cipher is that, when encrypting, parts are permuted with the fixed permutation $P\colon\{0,1\}^{50} \mapsto \{0, 1\}^{50}$. My question is this:
Does it follow that we only need 3 pairs of messages with corresponding ciphertext? IE, the first pair gives us 100 linear equations in 203 unknowns, two pairs gives us 200 linear equations in 203 unknown and after 3 pairs we're done (so long as the plaintexts are all different)? It depends on whether $P$ is linear doesn't it? does this question even really make sense?
Permutations are linear maps. Here's why:
Think of the bit strings as forming a vector space over the integers mod 2, say with basis $e_0,e_1,\ldots$. To illustrate let's assume the dimension is 3, so $$101=e_0+e_2$$ $$011=e_0+e_1$$ etc. Let's say the permutation maps $012\mapsto 201$. Then what we are doing is permuting basis vectors. The matrix for the corresponding linear transformation is $$A=\left(\begin{array}{ccc}0&0&1\\1&0&0\\0&1&0\end{array}\right)$$ Hence $$A((e_0+e_2)+(e_0+e_1))=(e_2+e_1)+(e_2+e_0)=e_0+e_1=A(e_1+e_2)$$ To generalize this example, the linear transformation corresponding to application of a permutation can be represented by the corresponding permutation matrix permuting the basis vectors.