Consider the following property of one-time symmetric encryption scheme $(\mathsf{Enc}, \mathsf{Dec}, \mathsf{K})$. For Every message distribution $M$, every pair of messages $m_0,m_1$ belonging to $M$ and every ciphertext $c$ belonging to $C$, it holds that:

$$\Pr[M=m_0 | C=c] = \Pr[M=m_1 | C=c]$$

Argue that the above property is not a characterization of perfect secrecy via a counterexample. Consider the one-time pad and any non-uniform distribution over $\{0,1\}^j$.

  • 3
    $\begingroup$ Is this homework? What have you tried? What do you not understand? $\endgroup$
    – cypherfox
    Commented Mar 22, 2018 at 3:12

1 Answer 1



Combine the usual definition of perfect secrecy $$\Pr[M=m\mid C=c]=\Pr[M=m]$$ with a non-uniform distribution $M$, e.g. $\Pr[M=0]=0.25, \Pr[M=1]=0.75$.

  • $\begingroup$ This is based on the definition of perfect secrecy using 'Perfect Indistinguishability' Pr[M=m0 | C=c] = Pr[M=m1 | C=c] So when this is broken, the counterexample would be like Pr[M=m0 | C=c] = Pr[M=m0] = 1/4 Pr[M=m1 | C=c] = Pr[M=m1] = 3/4 There is possibility to distinguish an encryption of m0 from an encryption of m1. I guess what I understood is right, correct me if its wrong $\endgroup$ Commented Mar 23, 2018 at 2:40
  • $\begingroup$ @Bhavi actually you can't distinguish an encryption of $m_1$ from an encryption of $m_0$, you can just say that it is more likely an encryption of $m_1$. If you could distinguish the encryptions, I'm pretty sure you could break perfect secrecy, but I'm lacking a formal model of a good indisitnguishability-based definition of perfect secrecy right now... $\endgroup$
    – SEJPM
    Commented Mar 23, 2018 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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