# Find Lower bound on key space with relaxed definiton of perfect secrecy

Consider a relaxed definition of security. Let $$\epsilon < 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]| < \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.

• $|\mathcal{K}|\geq|\mathcal{M}|\cdot2^{-\epsilon}$, and using a Taylor approximation, you get $|\mathcal{K}|\geq|\mathcal{M}|\cdot(1-\epsilon)$ for $\epsilon$ 'small'. – S Valera Nov 13 '19 at 18:05

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

Suppose we had a set of keys that was smaller than the number of plaintexts, or $$|K| < |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< \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.

• This is wrong - it would imply that all modern ciphers require the key to be at least as long as the plaintext. $\epsilon$-secrecy yields $|\mathcal{K}|\geq|\mathcal{M}|\cdot2^{-\epsilon}$ – S Valera Nov 13 '19 at 17:58
• @SValera: actually, this implies that no modern cipher gives "perfect secrecy", which is an accurate statement. Modern ciphers don't rely on perfect secrecy (that is, even with unbounded computation, you cannot obtain any information on the plaintext), but instead on computational assumptions (that is, you cannot perform any computation with the computational resources you have to obtain nontrival amounts of information about the plaintext; this computation may involve a key search, or another method) – poncho Nov 13 '19 at 18:07
• OP was asking about $\epsilon$-secrecy though, not perfect secrecy - modern ciphers are $\epsilon$-secret (with $\epsilon>0$) – S Valera Nov 13 '19 at 18:07
• @SValera: both modern ciphers and this question talk about $\epsilon$-security, but they mean different things by it. This question explicitly talks about probability distributions; those are assumed to be infeasible to compute with modern ciphers. – poncho Nov 13 '19 at 20:27
• The form of $\epsilon$-secrecy via distributions in the above question is equivalent to the usual one - my comment on OP's post holds true for his question. – S Valera Nov 13 '19 at 20:32