Clarification of some probability concepts used in crypto

Question

So I am a math major who is trying to learn some crypto. However I have some difficulties with some of the probability definitions that are assumed in the cryptography book that I am using at the moment. So here it goes:

Def(perfect security): Let $(E,D)$ be a Shannon cipher defined over $(K,M,C)$ where all these are finite sets and are respectively the key space, message space, and ciphertext space. Now consider the probabilistic experiment in which the random variable $k$ is uniformly distributed over $K$. If for all $m_0$, $m_1 \in M$, and all $c\in C$, we have $P(E(k,m_0)=c) = P(E(k,m_1)=c)$, then we say $(E,D)$ is perfectly secure.

As I understand it, the author assumes that we have a probability space on $K$, where the sigma-algebra is taken to be the power set of $K$, and $P$ is the probability measure defined on the power set of $K$. What I don't understand is what does random variable mean here. If I recall correctly, a random variable in probability theory is defined to be a measurable function from(in our case) $K$ to the real numbers. But I do not think the author is using this definition of random variable here. It would be great if anyone could clarify this part of the definition and also clarify what does $k$ uniformly distributed mean rigorously as well. I thought it means probability of each singleton outcome in $K$ is $1/|K|$. I might be wrong though. Thanks.

Answer 1

The measurable space is indeed ${\mathcal{K}=(K,2^K)}$ (cryptography mostly deals with discrete probabilities and the $\sigma$-algebra is taken to be the power set), and the probability measure is ${\mu(S)=|S|/|K|}$ for ${S\subseteq K}$. The notation $P(f(k))$, where $f(k)$ is a formula with free variable $k$, means $\mu(\{k\in K:f(k)\})$. Perfect secrecy requires $$\begin{aligned} &\forall m_0,m_1\in M,c\in C: \\&\quad \mu(\{k\in K:E(k,m_0)=c\})=\mu(\{k\in K:E(k,m_1)=c\}). \end{aligned}$$ The less ambiguous term is “random element”, i.e., a measurable map from the event space to a measurable space (not with the assumption that the codomain corresponds to the Borel algebra over $\mathbb{R}$). Here, the random element “$k$” is the identity map $\mathrm{id}_K$.

---

Edit on 26 Oct 2022: I should rather say that “the easiest way to implement this distribution is…” The random element $k$ could be implemented by any measurable map ${k:\Omega\to K}$ such that ${\nu(k^{-1}(\{z\}))=1/|K|}$ for all ${z\in K}$, where $\nu$ is a probability measure over some measurable space $(\Omega,\Sigma)$.

Answer 2

$M$ is not a $\sigma$-algebra, but a set of all possible messages. All three spaces: key space $K$, the message space $M$ and the ciphertext space $C$ are simply sets of all binary sequences of constant lengths $b_k$, $b_m$, $b_c$.

$$K=\underbrace{\{0,1\}\times...\times\{0,1\}}_{k}=\{0,1\}^{b_k}$$

$$M=\{0,1\}^{b_m}$$

$$C=\{0,1\}^{b_c}$$

E.g., for $b_k=2$, $K=\{00,01,10,11\}$.

Key $k$ is uniformly distributed draw from $K$. Continuing in the example above

$$P(k=00)=P(k=01)=P(k=10)=P(k=11)=\frac{1}{2^{b_k}}=0.25$$

Perfect security

The idea behind perfect security is that you should not learn anything by seeing the ciphertext. Note, encryption is a bijection, given a key. You fix the message and change keys, then the encryption produces ciphertexts from ciphertext space equally likely.

A typical example is one-time pad (OTP) of size $2$. You have the same key space as before. We want to send a message $m=01$. The OTP encryption is done with exclusive OR, $x=m\oplus k$.

For our message, all ciphertexts are equally likely.

$$01\oplus00=01$$ $$01\oplus01=00$$ $$01\oplus10=11$$ $$01\oplus11=10$$

The same work the other way around, when we fix the key and iterate messages. This means we have the perfect security - by seeing the ciphertext, we learn nothing about the message, all messages are equally likely! Remember, never reuse key in OTP!