2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.