Relationship among secrecy-constant, key space and message space

Here scheme $$\Pi$$ is $$\epsilon$$ - perfectly secret. Given that encryption scheme $$\Pi$$ = $$(\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$$ over $$(\mathcal K,\mathcal M,\mathcal C)$$ is called $$\epsilon$$ - perfectly secret if for any distribution over $$\mathcal M$$, any $$m \in M$$ and any $$c \in C$$,

$$|Pr[M=m|C=c] - Pr[M=m]|<\epsilon$$

then how to prove that , $$|\mathcal K|\geq (1 - \epsilon)|\mathcal M|$$

I am not getting idea how to proceed as here $$\epsilon$$ can be anything i.e non-negligible or negligible both.

1 Answer

HINT: here you can prove the above thing by contradiction. Start with the reverse of what needs to be proved and see you can arrive at contradiction or not. Treat $$\epsilon$$ as a parameter any, by the way, you are right it can be anything negligible or non-negligible.

• Prove by contradiction is nice idea, let's see whether I am able to reach final result or not. Thanks, Sam for quick response. – Zeeshan Noorani Apr 3 at 8:02