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
    Mar 22 '18 at 3:12


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$
    – Bhavi
    Mar 23 '18 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
    Mar 23 '18 at 9:54

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.