Proof that perfect privacy implies that the number of keys is at least the number of messages I was reading a proof to the statement: 


  Perfect privacy implies that $|K| = |M|$


where I am pretty sure that $K$ is the set of keys and $M$ is the set of messages.

The proof is the following, but I don't understand it (maybe because of the notation).


  Assume not, i.e., assume we have fewer keys than messages.
  Given a ciphertext $c$, there is a message $m$ and a key $k$ such that:
  
  $e(k, m) = c$, and $p_{k \in K}[e(k, m) = c] &gt; 0$
  
  Let $P_c = \{ m \in M$ such that $e(k, m) = c$ for some $k \}$
  
  Since every $k$ maps exactly one message $m$ to $c$, and since we have fewer keys than messages, then there is an $m'$ not in $P_c$ such that no key $k$ maps $m'$ to $c$.
  
  Therefore $P_{k \in K}[e(k, m') = c] = 0$, which violates the perfect-secrecy condition that for all m and $m'$, $P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m'). = c]$.


where $k \in K$ means that $k$ is a key in the set $K$.

The first thing that I don't understand is the following notation: $p_{k \in K}[e(k, m) = c] &gt; 0$. What exactly does this mean? Does $p$ refer to the probability? 

I understood the following statement:


  Since every $k$ maps exactly one message $m$ to $c$


It makes sense that a function should just output one result for the same inputs.


  Therefore $P_{k \in K}[e(k, m') = c] = 0$


Does this mean that the probability that we encrypt $m'$ using $k$ results in the cipher $c$ is equal to $0$ because, as said before in the proof, $m'$ is a message that has no key $k$ that transforms it into $c$? If yes, I am still not 100% convinced.


  which violates the perfect-secrecy condition that for all m and $m'$, $P_{k \in K}[e(k, m) = c] = P_{k \in K}[e_k(k, m'). = c]$


If we assumed at the beginning that $p_{k \in K}[e(k, m) = c] &gt; 0$, that the statement above makes also sense.

Again, I don't get the part of assuming $p_{k \in K}[e(k, m) = c] &gt; 0$ (apart from the fact that I am not sure if $p$ should be $P$, i.e. if it is just a typo, and if $P$ (or $p$) refer to probabilities, as I was wondering above).

Moreover, I think the proof is not showing the case when the number of keys is greater than those of the messages.
Let $K$ be the set of all possible keys (for AES-256, this set has $2^{256}$ elements.)
Let $M$ be the set of all possible messages (for AES, it has $2^{128}$ elements).
Let $C$ be the set of all possible cipher texts (for AES, again $2^{128}$ elements).

I was reading a proof to the statement:

Perfect privacy implies that $|K|=|M|$


Actually this is $|K| \ge |M|$.
Perfect privacy condition is: 
that for all $m$ and $m′$, $P_{k \in K}[e(k,m)=c]=P_{k \in K}[e(k,m′).=c]$
the probability that a cipher text $c$ is decrypted as $m$ is the same as being decrypted in $m'$.
Or in other words:
you can't find a difference between $m$ and $m'$.
In order to prove such statement you use reductio ad absurdum. Here you assume $|M| &gt; |K|$.

The first thing that I don't understand is the following notation: $p_{k \in K}[e(k,m)=c]&gt;0$. What exactly does this mean ?

Yes the $p$ is a typo and should be $P$. It means that there exists $k$ and $m$ such as $e(k,m)=c$ (which is trivial because we need a working algorithm...). Therefore the probability that given a $c$, $m$ is the plain text is at least $\frac{1}{|M|}$ (assuming a uniform distribution), hence $&gt; 0$.
About this part:

Therefore $P_{k \in K}[e(k,m′)=c]=0$
Does this mean that the probability that we encrypt $m′$
using $k$ results in the cipher $c$ is equal to $0$ because, as said before in the proof, $m′$ is a message that has no key $k$ that transforms it into $c$? If yes, I am still not 100% convinced.

The first thing you must think of is that the $c$ is fixed. In order to encrypt a message $m$ to this $c$ you need a key $k$. Because $|M|$ is greater than $|K|$ (assume $|M| = 5$ and $|K| = 3$), there exists messages that won't have a mapping to $c$ (in this case $5 - 3 = 2$). Therefore there exists $m'$ such as there is no $k$ so that $e(k,m) = c$. Hence $P_{k \in K}[e(k,m′)=c]=0$
Because the statement of perfect secrecy is for all $m$ and $m'$ you can't have at the same time all probabilities being $&gt; 0$ and $= 0$. Therefore you have a contradiction.