Perfect security definitions

Question

In my notes, there are 2 definitions of perfect security:

1. "For $M \in \{0,1\}^m$, define the distribution $D_M$ on strings as follows: to choose a random member of $D_M$, choose a random $K \in \{0,1\}^n$ and output $Enc(M,K)$. Then $Enc,Dec$ is perfectly secure if $D_M$ is exactly the same for every $M$. That is, for every $\alpha \in \{0,1\}^*$, the probability of $\alpha$ according to $D_M$ is independent of $M$.

2. For every two messages, no function can tell which one has been encrypted. That is, $Enc,Dec$ is perfectly secure if for every $M_0,M_1 \in \{0,1\}^m$ and for every $f: \{0,1\}^* \to \{0,1\}$, the following holds: consider the experiment where $b$ is randomly chosen from $\{0,1\}$ and $K$ is randomly chosen from $\{0,1\}^n$; then the probability that $f(Enc(M_b,K)) = b$ is equal to $1/2$."

I have two questions:

1. Could someone clarify the definition of $D_M$ (the distribution of strings?). I'm not sure I get what is meant by the "distribution of strings" and how it differs from $M$
2. If $M_0$, and $M_1$ are any two $m$-bit messages, how is it possible that their encryption be equal $b$? Wouldn't the number of bits in the encrypted message be $m$? if that number is for example 10 then how does $P \left ( f( \mathrm{Enc} (M_b, K)) = b \right ) = 0.5$?

Answer 1

If M0, and M1 are any 2 m-bit messages, how is it possible that their encryption be equal b?

The definition does not say that their encryption is equal b. It says that the function f outputs b. This function is often called distinguisher (or attacker) and he should not be able to distinguish which message M0 or M1 was encrypted. In other words there exists no distinguisher who can distinguish which message was encrypted better than with probability of guessing (0.5).

Answer 2

In the first definition, $D_M$ is a probability distribution. As the Wikipedia page notes, there are various ways to specify a probability distribution; one of them, which is what's used here, is to specify how to sample a random variable distributed according to that distribution.

Specifically, what the definition is saying is that $D_M$ is the distribution of ciphertexts obtained by encrypting the message $M$ with a randomly chosen key $K$. In other words, to sample a random variable $X$ distributed according to the distribution $D_M$, you take the message $M$, pick a random key $K$ from the keyspace and let $X = Enc(M,K)$.

(To be specific, the key $K$ should presumably be chosen uniformly from the set of $n$-bit keys $\{0,1\}^n$, although the definition doesn't explicitly say so. It's a common convention in cryptography that random variables chosen from a finite set are assumed to be uniformly distributed unless stated otherwise.)

The definition then says that the encryption is perfectly secure if and only if $D_{M_0} = D_{M_1}$ for any two messages $M_0$ and $M_1$ — that is, if, for any given messages $M_0$ and $M_1$, any given ciphertext $C$ and a random key $K$, the probability that $Enc(M_0,K) = C$ equals the probability that $Enc(M_1,K) = C$.

---

In the second definition, the notation $f:\{0,1\}^* \to \{0,1\}$ means that $f$ is a function from the set $\{0,1\}^*$ of arbitrary bitstrings to the set $\{0,1\}$ of single bits. That is, $f$ takes a bitstring as input and outputs a single bit.

We can think of the input of $f$ as an encrypted message, and the output of $f$ as a guess about which of $M_0$ or $M_1$ is the plaintext corresponding to the input. The definition then says that, if (and only if) our encryption system is perfectly secure, then for any pair of messages $M_0$ and $M_1$ and any distinguisher $f$, if we take a random message $M$ chosen from the given pair of messages, and encrypt it with a random key $K$ to get a ciphertext $C = Enc(M,K)$, then the guess $f(C)$ has no more (and no less) than a 50% change of being correct.