# Encryption Scheme & Perfect Secrecy [Katz & Lindell]

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: 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?

• This was cross posted on Math. Please don't cross post on multiple sites. It is against SE rules. – mikeazo Sep 7 '17 at 22:05
• This could be useful... – fkraiem Sep 8 '17 at 3:56

What does, say, $P(K=k)$ mean exactly?

It signifies the probability that the key $K$ selected by the key generation algorithm $Gen$ is the value $k$.

The notation he is using is that $P(condition)$ (actually, they use $Pr[condition]$, perhaps to emphasize that $P$ isn't a function on the value condition, but rather its probability distribution) is the probability that the condition is true. For example, if I flip a fair coin, we have $P(\text{heads}) = 0.5$

What is the domain and codomain of the random variable $K$?

The key space $\mathcal K$

What is the set $\{K=k\}$?

It's not a set; it's an equality which is true with a certain probability.

Also, what is the domain of Gen?

The key space $\mathcal K$

• The domain of Gen is the key space? – mikeazo Sep 7 '17 at 17:22
• $P$ or $Pr$ is a probability measure and as such it takes as input a set. Usually when one writes, say, $P(X=0)$, this is shorthand for $P(\{\omega \in \Omega : X(\omega) = 0\}$ where $\Omega$ is the sample space and $X:\Omega\to \Bbb R$ some random variable. – CRYPTONEWBIE Sep 7 '17 at 17:39
• So in short, I still don't know what $P(K = k)$ means. What is the sample space on which $K$ is defined and what is its codomain? What is the set of events on which $Pr$ is defined? @poncho – CRYPTONEWBIE Sep 7 '17 at 17:41
• BTW: what do you mean by 'codomain'? $K$ isn't a function, it's a random variable... – poncho Sep 7 '17 at 17:53
• The input of Gen is a constant $n$-bit string, which is overwritten by a non-deterministic Turing machine to give a $n$-bit key. The codomain is $\mathcal{K}$, though. – Henno Brandsma Sep 7 '17 at 20:43