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

-

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9297037124633789, "perplexity_flag": "head"}