Let $\mathcal K$ and $\mathcal M$ be the key and message spaces respectively I know for fact that if $|\mathcal K| < |\mathcal M|$ then $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi} = 1] > \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| < |\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| < |\mathcal M|$ and $\Pr[\operatorname{PrivK}_{\mathcal A,\Pi} = 1] > \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.

(133)