Almost (epsilon) perfect secrecy - lower bound of keyspace size As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography.

Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, then $\lvert K\rvert \geq \lvert M\rvert$),
I've shown that the lower bound for the size of the keyspace is as below:
$$\lvert K\rvert \geq (1-\epsilon)\lvert M\rvert$$

But here's the problem: I proved this under the condition that $$\lvert\Pr[M=m\mid C=c]-\Pr[M=m]\rvert\leq\epsilon$$

So I think I should show that this definition is equivalent to the condition given in the exercise.

My question is whether the two definitions are equivalent, and if so, how can I prove it?
Short answer: the two definitions are not equivalent.
Long answer:

The condition $|\Pr[M=m\mid C=c]-\Pr[M=m]|\leq\epsilon$ doesn't allow us to have less keys than messages. Encrypt an arbitrary message to get a ciphertext $c$, then use all keys to decrypt $c$. If $|K| \lt |M|$, there exists a message $m$ which can not be decrypted from $c$ using any key.
Then $|\Pr[M=m\mid C=c]-\Pr[M=m]| = \Pr[M=m]$ and since we can assign an arbitrary distribution to our message space, we can make $\Pr[M=m] &gt; \epsilon$

The definition of $\epsilon$-perfect secrecy given in the book (the one you show in the image) does allow us to have fewer keys than messages. For example:
Suppose the message space $M$ contains all 4 English letter words, $|M|$ = $26^4$. Let's use a one-time-pad encryption scheme without the identity key, thus $|K|$ = $|M| - 1$.
Any adversary playing a game will choose two messages $m_0$, $m_1$. If our returned ciphertext $c=m_0$ the adversary knows for sure that the encrypted message is $m_1$. If our returned ciphertext $c=m_1$ the adversary knows for sure that the encrypted message is $m_0$. But if we return any other ciphertext, the one-time-pad scheme ensures that the best an adversary can do is to make a random guess. Therefore, the probability for an adversary to win a game is not greater than
$1 \cdot \Pr(c \in \{m_0, m_1\}) + \frac{1}{2} \cdot (1 - \Pr(c \in \{m_0, m_1\}))$ = $\frac{1}{2} + \Pr(c \in \{m_0, m_1\}) \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2|K|}$
Thus, this scheme achieves $\epsilon$ perfect secrecy if $\epsilon \geq \frac{1}{2|M-1|}$

Let's find a lower bound for $\epsilon$. Suppose an adversary chooses $m_0$ and $m_1$ uniformly at random. Upon receiving a ciphertext $c$ it computes $M_c = \{ m | \exists k. enc_k(m) = c\}$ (it might be computationally infeasible to compute $M_c$, but we're not concerned about computational resources in this exercise).
Note that at least one of $m_0, m_1$ is in $M_c$. If some $m_i \not \in M_c$ the adversary knows for sure that the encrypted message is the other one. If both messages are in $M_c$, the adversary makes a random guess.
The probability of such adversary succeeding is
$\frac{1}{2} \cdot \Pr(m_0, m_1 \in M_c) + 1 \cdot (1-\Pr(m_0, m_1 \in M_c))$ = $ 1 - \Pr(m_o, m_1 \in M_c) \cdot \frac{1}{2}$
Let's estimate $\Pr(m_0, m_1 \in M_c)$ - the probability that both messages are in $M_c$. One message will certainly be in $M_c$ because we encrypted it to $c$, the other message is chosen uniformly at random from $M$, so the probability of both being in $M_c$ is $|M_c| / |M| \leq |K| / |M|$
Thus an adversary can win a game with a probability $p \geq 1 - |K| / |M| \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2} \cdot (|M| - |K|) / |M|$. If we want $\epsilon$ secrecy we must have $\frac{1}{2} + \epsilon \geq p$ which implies that:
$|K| \geq |M| \cdot (1-2\epsilon)$
note that I have not shown this lower bound is attainable.