I'm quite thrilled about this question I got for homework, even though we were given the answer to the problem. It goes like this: Let $\mathcal{M}$ be the set of plaintexts of a symmetric encryption scheme. Prove that if the scheme is perfectly secret for some distribution $D_{\mathcal{M}}$ over $\mathcal{M}$, then the scheme is p.s. for any distribution over $\mathcal{M}$.

It was quite surprising at first, but then it started to make sense since in $$Pr[C=c|M=m]=Pr[C=c]$$ the right side does not depend on $D_{\mathcal{M}}$... and that's basically all I have, still not sure if that's enough or a good approach, so any advise will be appreciated. Thanks a lot, cheers!

  • $\begingroup$ The statement to be proved is not true! Consider a scheme that always outputs the plaintext as the ciphertext, i.e., it hides nothing. This scheme actually is perfectly secret for any distribution D that always outputs some fixed message (that goes for any scheme with such a distribution), but it is not perfectly secret for any other distribution. $\endgroup$ – Chris Peikert Mar 30 '18 at 15:31

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.