# Message space in security definitions

What is the message space in the following example and how does a message space relate to a security definition?

I mean, what difference does it make to such a definition if your message space is $\{0,1\}^n$ or if it is $\{0,1\}$?

We say $(\mathsf{K},\mathsf{E},\mathsf{D})$ is $(t,\epsilon)$-IND-CPA secure if for all $t$-bounded adversaries Adv:

$|\mathrm{Pr}[ (pk,sk)←\mathsf{K}(1^n); (m_0,m_1)←\mathrm{Adv}(pk);c ← \mathsf{E}_{pk}(m_0): \mathrm{Adv}(c) = 1]$ $-\mathrm{Pr}[(pk,sk)←\mathsf{K}(1^n); (m_0,m_1)←\mathrm{Adv}(pk); c←\mathsf{E}_{pk}(m_1): \mathrm{Adv}(c) = 1 ]| \leq ε$

where Adv outputs $|m_0|=|m_1|$

-

In your formula, $n$ appears to relate to the key space, not the message space.

The message space does not intervene in the definition of IND-CPA, and that's a good thing because practical message spaces consist in messages which "make sense" in a given context. There are situations where the attacker already guesses quite a lot of the attacked message, and the message space size (as in "number of distinct values that the message may meaningfully assume") can shrink down to 2 (e.g. if the attacker tries to guess a yes/no answer). So whatever security definition you use must be able to cope with very small message spaces.

The formula you quote is the translation of the following thought experiment:

• A key pair is generated, with a given "size parameter" $n$ (e.g. we do RSA, with a 1024-bit key). The public key is made public, i.e. the adversary can see it.
• The adversary produces two messages $m_0$ and $m_1$ of his choosing, from the set of message values that the encryption scheme can process (e.g. with RSA, a 1024-bit key, and PKCS#1 v1.5 padding, $m_0$ and $m_1$ must be sequences of bytes no longer than 117 bytes).
• We choose at random one of the two messages, encrypt it, and give it back to the adversary.
• The adversary must now guess which of the two messages we encrypted.

If we do this many times, we can compute the average success of the attacker. If the encryption system is "perfect", the adversary can do no better than a random binary choice. But we give him some CPU power (the $t$ parameter) and he can use that to try to guess the private key, so the attacker can always guess correctly a bit more often than incorrectly. The $ε$ value is a measure of that "bit more".

Specifically, in the formula, the first probability says how often the adversary gets it wrong when he answers "1", and the second how often he gets it right. The difference between the two probabilities should be no more than $ε$. Note that if the adversary cannot guess right substantially more often than half the time, he cannot guess right substantially less often than half the time either (otherwise, he could just systematically reverse his answer; a compass which always points South is quite useful once you know it).

"CPA" means "Chosen-Plaintext Attack": in the thought experiment, the adversary can choose $m_0$ and $m_1$ as he wishes to, and can do it again for each attack instance.

-