# 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| < |\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.

• I've edited your post to look better and use the fancy representation possibilities we have here. I'm 99% sure that the probability formulae are still wrongly formatted. So please go ahead and fix them if you can and want to :) – SEJPM Sep 25 '16 at 21:16
• The adversary wins the experiment (and thus the experiments outputs 1) if and only if $b=b'$, where $b$ is randomly sampled from $\{0,1\}$. So if the probability if the experiment outputting 1 is strictly greater than $0.5$ then the adversary must have some way to (sometimes) do better than guessing which message was encrypted (so he can chose his $b'$ accordingly). – SEJPM Sep 25 '16 at 21:19
• Thanks for your reply, the question here is : given an encryption scheme with $|\mathcal K| < |\mathcal M|$, i should find a case where the attacker $\mathcal A$ have a $\Pr[\operatorname{PrivK}^{\mathcal A,\Pi} = 1] > \frac{1}{2}$, but still I don't see it and I have no beginning of a proof !! – dev Sep 25 '16 at 21:41
• The easiest way to approach this is by working out an attack that is relieable. For example consider an OTP where the key is one bit shorter than the message and the first bit of the key is re-used for the last bit of the message and the first bit of the message, than remember who chooses the message and whether this property helps in distinguishing. – SEJPM Sep 25 '16 at 21:47
• Well, I kinda found something but without re-using the last bit of the key, I assumed that $\mathcal \pi$ (Gen,Enc,Dec) is an OTP with $\mathcal K$ {0,1}^2 and $\mathcal M$ {0,1}^3. $\mathcal A$ outputs two messages m^0 = 000 and m^1 = 011. let ${\mathcal c=c^{1}c^{2}}$ $\mathcal A$ outputs 0 else he outputs 1 and since the key is one bit shorter than the message so the third bit won't be XORED (will stay the same). The available key are {00,01,10,11} so it's easy to distinguish between both messages in this case (I skipped the probability part). – dev Sep 25 '16 at 22:52

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

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.

• It's nice how you proved it using logical expressions, I didn't think of it that way, but what I want to do here is to prove it without assuming that ${|\mathcal K|}$ ${\geq}$ ${|\mathcal M|}$ implies perfect secrecy so the only way I see things here is to show a counter example or an attack where the probability is > 1/2 to prove that if ${|\mathcal K|}$ < ${|\mathcal M|}$ then there is no perfect secrecy – dev Sep 26 '16 at 16:38
• @dev You mixed up something there. $|K| \geq |M|$ does not imply perfect secrecy. It's the other way around. Of course you could have a totally insecure encryption scheme with a larger keyspace, e.g. $Enc(m,k) = m$, where $|K|$ is as large as you want. But if you have perfect secrecy, then $K$ has to be larger than $M$. So the implication goes from secrecy to the argument about cardinalities, not the other way around. – tylo Sep 26 '16 at 18:22
• I'm sorry, what I wanted to say is that without assuming that the fact of perfect secrecy implies a $|\mathcal K| \geq |\mathcal M|$, I should give something that proves the counter is wrong, like having an encryption scheme with $|\mathcal K| < |\mathcal M|$ and think of an attack that will fail – dev Sep 26 '16 at 18:36
• Well, your statement is equivalent to perfect secrecy. Of course you can prove it from scratch, but you will have the same proof with a different point of view like the one for perfect secrecy. That's the first part of my answer pretty much. – tylo Sep 26 '16 at 18:42