1
$\begingroup$

Prove that for any symmetric-key encrytion scheme $\Pi=(Gen, Enc, Dec)$ with message space $M$ and key space $K$, there exist $m_0, m_1 \in M$ such that $\Delta(Enc(K, m_0), Enc(K, m_1))\ge 1-\frac{|K|}{|M|}$.

I know that $\Delta(X,Y)=\max\limits_{T\subseteq S}(Pr(X\in T)-Pr(Y\in T))$, but I have no idea about the inequation above. I tried to prove by contradiction but failed.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.