# One-time pad and Perfect secrecy

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$.

• Is this homework? What have you tried? What do you not understand? – cypherfox Mar 22 '18 at 3:12

Hint:

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$.

• 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 – Bhavi Mar 23 '18 at 2:40
• @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... – SEJPM Mar 23 '18 at 9:54