Key space lower than Message spaces

Question

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}$ :

1. The adversary $\mathcal A$ outputs a pair of messages $\mathcal m_0$ $ m_1$.

2. 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).

3. $\mathcal A$ outputs a bit $\mathcal b'$ $\mathcal \in$ {0,1}.

4. 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.

Answer 1

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 $< 1/2$ is equivlant to an attacker with probability $>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| < |M|$.

Therefore we get:

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

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