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.


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.