Find Lower bound on key space with relaxed definiton of perfect secrecy Consider a relaxed definition of security. Let $\epsilon &lt; 1$ be a constant and say we only require that for any distribution over $M$ ,any $m \in M $, and any $ c \in C$

$$
|Pr[M=m|C=c] - Pr[M=m]| &lt; \epsilon
$$

I want to find a lower bound on the size of key space $K$ relative to $M$ for any encryption scheme that meets this definition.
I believe that this 'relaxed' definition gives the same minimal key length as the standard perfect security definition; that is, the number of keys $|K|$ must be at least as large as the number of possible plaintexts $|P|$.  This is true for any $\epsilon &lt; 1$.

Suppose we had a set of keys that was smaller than the number of plaintexts, or $|K| &lt; |P|$.  In that case, we pick a possible ciphertext $c$ and see that can be decrypted to at most $|K|$ distinct plaintexts (depending on the key); hence there must be a plaintext $p_0$ that it cannot decrypt to.  Let us call plaintext $p_1$ a plaintext that it can decrypt to.

Then, consider the probability distribution:

$M = p_0$ with probability $\epsilon$

$M = p_1$ with probability $1 - \epsilon$

$M$ is any other plaintext with probability 0

If we consider the equation with $m = p_0$, we have:

$Pr[ M = m | C = c ] = 0$ (because that plaintext is impossible with that ciphertext)

$Pr[ M = m ] = \epsilon$

And hence $|Pr[M=m|C=c] - Pr[M=m]| = \epsilon \not&lt; \epsilon$, and so we find that the required inequality does not hold.

Hence, that relation can hold in general only if $|K| \ge |P|$, which is the same bound as what perfect secrecy requires.