Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|improve this question

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)) < n$ equals $1 - \prod_{i=0}^{n-1}( 1-2^{i-M} ) \le \sum_{i=0}^{n-1} 2^{i-M} < 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.

share|improve this answer

Your Answer


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.