Dimension of Encryption of a linearly dependent set of plaintexts Suppose I have an encryption scheme of the form $ E(P)=C $ where $P$ is the plaintext and belongs in $\{0,1\}^N$, $C$ the ciphertext which belongs to $\{0,1\}^M$ and the encryption is performed under the key $K$ in $\{0,1\}^R$.

If I pick a subspace of messages $M_0$ and I perform encryption on this set, can I conclude anything about the dimension of $E(M_0)$ as a subspace of $\{0,1\}^M$.
If $E$ was a random function from $\{0,1\}^N$ to $\{0,1\}^M$, then encrypting $n = |M_0|$ distinct messages with $E$ would be equivalent to picking $n$ independent random elements from $\{0,1\}^M$.  If $n \ll M$, these random elements are with very high probability linearly independent, and thus span a subspace of dimension $n$; conversely, if $n \gg M$, with high probability they'll span the entire $M$-dimensional space.

In any case, of course, $\dim(E(M_0)) \le \min(n,M)$.  If $n \approx M$, there's a non-negligible probability that the inequality is strict, but it decreases exponentially in either direction.  (In particular, the probability that $\dim(E(M_0)) &lt; n$ equals $1 - \prod_{i=0}^{n-1}( 1-2^{i-M} ) \le \sum_{i=0}^{n-1} 2^{i-M} &lt; 2^{n-M}$.)

Now, determining the dimension of the subspace spanned by $E(M_0)$ is computationally fairly easy (at least unless both $M$ and $n$ are really huge), so any non-negligible difference in it between the actual encryption scheme $E$ and a random function would allow a distinguishing attack on $E$.  Secure encryption schemes are not supposed to be distinguishable from random functions (without knowledge of the key), so if $E$ is secure, there shouldn't be any detectable statistical difference between the dimension of $E(M_0)$ and that predicted for a random function.