Defining the random variables $K,M,C$ and Perfect Secrecy

Question

In many books on Cryptography, we refer to probability distributions over the key space $\mathcal{K}$, over the plaintext space $\mathcal{M}$ and over the ciphertext space $\mathcal{C}$.

Then, we let $K$ be the random variable denoting the value of the key output by $\mathsf{Gen}$, so for any $k\in \mathcal K$, then $\mathrm{Pr}(K=k)$ is the probability of the event that after, running $\mathsf{Gen}$, to pick the key $k\in \mathcal K$. Likewise, we let $M$ be the random variable denoting the message being encrypted, so $\mathrm{Pr}(M=m)$ denotes the probability that the message takes the value $m\in \mathcal M$. Lastly, we let $C$ be the random variable denoting the resulting ciphertext, so $\mathrm{Pr}(C=c)$ denotes the probability that the ciphertext is equal to the fixed value $c\in \mathcal C$.

$\color{blue}{\textrm{Questions.}}$

From maths, we know that a random variable is a function $X:\Omega \longrightarrow V$. In the textbooks, I observed that the authors avoid to explicitely define abovementioned random variables. So:

1. What are $K,P,C$ as functions? What are their domains and codomains?
2. Later, the books also introduce new random variables, when they discuss about perfect secrecy. These are $\mathsf{Enc_K}(M)$ and $\mathsf{Enc_K}(m)$ for some fixed $m\in \mathcal M$. Again, what are their domains and codomains of these random variables?

$\color{blue}{\textrm{Thoughts.}}$

1. Firstly, it seems that $K$ is the identity function. That is, $$K=\mathrm{Id_\mathcal{K}}:\mathcal{K}\longrightarrow \mathcal{K},\quad k\longmapsto k.$$ So, formally when $K$ follows the uniform distribution over $\mathcal{K}$, we have $$ \mathrm{Pr}(K=k)= \mathrm{Pr}(\{x\in \mathcal K: K(x)=k\})=\mathrm{Pr}(\{k\})=\frac{1}{|\mathcal{K}|}. $$ In addiction, I would say that we have \begin{gather*} M:\mathcal{K}\times \mathcal{M}\longrightarrow \mathcal{M},\quad (k,m)\longmapsto m, \newline C:\mathcal{K}\times \mathcal{M}\longrightarrow \mathcal{C},\quad (k,m)\longmapsto \mathsf{Enc}_k(m). \end{gather*}
2. I would say that, fixing some $m_1\in \mathcal M$, \begin{gather*} C=\mathsf{Enc}_K(M):\mathcal{K}\times \mathcal{M}\longrightarrow \mathcal{M},\quad (k,m)\longmapsto m, \newline \mathsf{Enc}_K(M):\mathcal{K}\times \{m_1\}\longrightarrow \mathcal{C},\quad (k,m_1)\longmapsto \mathsf{Enc}_k(m_1). \end{gather*} So, later, when we define perfect secrecy, we will have \begin{eqnarray*} \mathrm{Pr}(\mathsf{Enc}_K(m_1)=c) &=& \mathrm{Pr}(\{(k,m_1)\in \mathcal K \times \{m_1\}: \mathsf{Enc}_k(m_1)=c \}) \newline &=&\frac{|\{(k,m_1)\in \mathcal K \times \{m_1\}: \mathsf{Enc}_k(m_1)=c \}|}{|\mathcal K \times \{m_1\}|} \newline &=&\frac{|\{k \in \mathcal K : \mathsf{Enc}_k(m_1)=c \}|}{|\mathcal K|}. \end{eqnarray*}

Are my thoughts correct? Any addition is more than welcome!

Reference: Introduction to Modern Cryptography, J. Katz and Y. Lindell.

Answer 1

I don't really understand the significance of a more formal definition of random variables in this context. What would they bring to the table? What is there that we can't do under the current formalism? I am willing to be educated.

I'd say for a typical setup [block ciphers] all the domains and codomains are $\{0,1\}^n$ where $n$ can be blocklength, keylength as appropriate. In the usual block cipher case, the RVs are indeed identity maps. In the more classical cases you can have domains and codomains of the type $\{a,b,\cdots,z\}^\ell$ where $\ell$ can be the message length for message space and ciphertext space. Yes you can have keys that are from a different alphabet, but all these are somewhat orthogonal to your main goals in cryptography.

You can build up similar sets for stream ciphers if you like, where the ciphertext and plaintext are much longer than the key, and again, I don't see a utility in doing so.

As for some of your statements, I don't understand how they could be correct:

I would say that we have \begin{gather*} M:\mathcal{K}\times \mathcal{M}\longrightarrow \mathcal{M},\quad (k,m)\longmapsto m, \newline C:\mathcal{K}\times \mathcal{M}\longrightarrow \mathcal{C},\quad (k,m)\longmapsto \mathsf{Enc}_k(m). \end{gather*}

The first line is mysterious. How can the message depend on the key? The whole point is that the key is an independent hopefully uniform random variable which is used to encrypt the message, i.e., obtain the ciphertext. I'd say all cryptography texts have this standard definition.

The second line looks fine. Maybe you are thinking of the message space and the ciphertext space as being the same [which as sets they are] and that's why you are using $M$ at the output. But standard crypto notation distinguishes the two, even though both may actually be the set $\{0,1\}^n$ as alluded to above.

2. I would say that, fixing some $m_1\in \mathcal M$, \begin{gather*} C=\mathsf{Enc}_K(M):\mathcal{K}\times \mathcal{M}\longrightarrow \mathcal{M},\quad (k,m)\longmapsto m, \newline \mathsf{Enc}_K(M):\mathcal{K}\times \{m_1\}\longrightarrow \mathcal{C},\quad (k,m_1)\longmapsto \mathsf{Enc}_k(m_1). \end{gather*}

This I don't understand at all.