Key space lower than Message spaces Let $\mathcal K$ and $\mathcal M$ be the key and message spaces respectively 
 I know for fact that if $|\mathcal K| &lt; |\mathcal M|$ then $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi} = 1] &gt; \frac{1}{2}$, knowing also that $\mathcal A$ is randomized and $\Pi(\operatorname{Gen},\operatorname{Enc},\operatorname{Dec})$ is an arbitrary encryption scheme with $|\mathcal K| &lt; |\mathcal M|$

I'm trying to prove that but I find some problems :

I can't find any relation between the fact that $|\mathcal K| &lt; |\mathcal M|$ and 
$\Pr[\operatorname{PrivK}_{\mathcal A,\Pi} = 1] &gt; \frac{1}{2}$, isn't the random bit $b'$ - the adversary generates to choose between the two messages - that defines whether the probability is higher or equal to $\frac{1}{2}$? I'm confused ?

For those of you who doesn't know about the $\operatorname{PrivK}_{\mathcal A,\Pi}$ experiment (Adversary $\mathcal A$ against the encryption scheme $\mathcal \pi$): 


  The Adversarial Indistinguishability Experiment $\operatorname{PrivK}_{\mathcal A,\Pi}$ :
  
  
  The adversary $\mathcal A$ outputs a pair of messages $\mathcal m_0$ $ m_1$.
  A key $\mathcal k$ is generated using $\mathcal Gen$(A key generator) and then a bit $\mathcal b$$\mathcal  \in${0,1} is chosen. Ciphertext $\mathcal c $$\mathcal \gets$  Enc($\mathcal m_b$) is computed and given to $\mathcal A$. ($\mathcal c$ refers to challenge cipher).
  $\mathcal A$ outputs a bit $\mathcal b'$ $\mathcal \in$ {0,1}.
  The output of the experiment is defined to be 1 if $\mathcal b$ $\mathcal =$ $\mathcal b'$ and $\mathcal 0 $ otherwise. We write $\operatorname{PrivK}_{\mathcal A,\Pi} = 1$ if the output of the experiment is $\mathcal 1$ and in this case we say $\mathcal A$ succeeded.
1st answer:

I was writing a longer answer about proving the claim directly, with the cardinalities of the message space, ciphertext space and keyspace. Basically for a random message, not all ciphertexts are possible, thus for a random challenge, not both messages might be valid decryptions. If you assume that the attacker can try out all valid keys, just one of the messages might be a valid preimage for the challenge ciphertext. In that case, the attacker can find $b$. With randomly chosen messages, this results in a probability different than $1/2$.

2nd answer:

Actually, the proof of the statement is more elegant (in my opinion) with a contraposition ($A \rightarrow B$ is logically equivalent to $\neg B \rightarrow \neg A$) of the following statement:

Perfect secrecy requires $|K|\geq |M|$. If expressed in logic terms, we can say:

Perfect secrecy  $\rightarrow$ $|K|\geq |M|$.

Perfect secrecy means, the attacker has a probability of $1/2$. If the probability is anything else, it isn't perfect secrecy. Keep in mind, that an attacker with probability $&lt; 1/2$ is equivlant to an attacker with probability $&gt;1/2$, by simply flipping the output bit.


Perfect secrecy means basically: $\forall \mathcal{A}: Pr_{\mathcal{A}} = 1/2$. The inverse is: $\exists \mathcal{A}: Pr_{\mathcal{A}} \neq 1/2$
Inverting the statement $|K|\geq |M|$ is quite easy: $|K| &lt; |M|$.


Therefore we get:

$|K| &lt; |M|$ implies $\exists \mathcal{A}: Pr_{\mathcal{A}} \neq 1/2$  

This is already quite close in what you tried to prove.