Encryption Scheme & Perfect Secrecy [Katz & Lindell]

Question

An encryption scheme consists of the following data

• a plaintext space $\mathcal M$
• a ciphertext space $\mathcal C$
• a key space $\mathcal K$
• a key generating algorithm Gen
• encryption and decryption algorithms $\operatorname{Enc}_k$ and $\operatorname{Dec}_k$ for each key $k\in \mathcal K$

I would like some clarification on the following extract from Katz & Lindell:

https://i.stack.imgur.com/Q3fzK.png

More specifically, my question is: What does, say, $P(K=k)$ mean exactly? What is the domain and codomain of the random variable $K$? What is the set $\{K=k\}$? Also, what is the domain of Gen?

Answer 1

Gen is a key generation "algorithm". An algorithm is modelled as a non-deterministic Turing machine. The algorithm has a "security parameter", here the key size $n$ (which can be $128$ for AES). To get a uniform key space: the Turing machine has $1^n$ as input ,a sequence of $n$ $1$'s (or $0$'s if you prefer), and starts at the left, overwriting each $1$ (or $0$ with) with a $0$ or $1$ using the randomised algorithm (given by coin flips), moving 1 to the right. It stops at the end of the input, at the first empty cell. The result is what was written on the tape.

Usually this is written as $\text{Gen}: 1^n \to \mathcal{K}$, to denote that $k$ is chosen uniformly at random from $\{0,1\}^n$. So then $P(K=k) = \frac{1}{2^n}$, as all keys are equally likely. So the sample space for $K$ (as a random variable) is all subsets of $\mathcal{K}$ (so $\mathscr{P}(\mathcal{K})$), and $P(A) = P(K \in A) = \frac{|A|}{2^n}$.

So $P$ is just a probability measure on $\mathscr{P}(\mathcal{K})$ and the random variable $K$ is somewhat superfluous: we can talk about $P(A)$, which we interpret to mean that the key we chose lies in $A$. Usually a random variable maps events in a probability space to numeric values, but in a general sense a random variable is a measurable function from $(S, P)$, a probability space, to any measurable space (like the reals). In this book, Gen is seen as the random function $K$ that produces values in the measurable space $(\mathcal{K},P)$ with the powerset as the $\sigma$-algebra and $P$ uniform as described.

Answer 2

$K$ is the random variable of "chosen key from the keyspace used in one instance of encryption passing." So, given a key $k \in \mathcal{K}$, $P(K =k)$ is the probability that the key $k$ is chosen for a round of encryption. Most crypto protocols (and certainly analysis of perfect secrecy) require this to be uniformly distributed.