# One-time pad without zero: proof check

I started learning cryptography and tried to work through this problem: consider one-time pad where $$\mathcal{M}=\mathcal{C}=\{0,1\}^n$$ and $$\mathcal{K}=\{0,1\}^n\setminus 0^n$$ (call this scheme $$\Pi$$). Find $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1]$$.

My attempt: $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1]$$=$$\frac{1}{2}\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1\mid b=0] + \frac{1}{2}\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1\mid b=1]$$.

Focus on $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1\mid b=0]$$. The "problematic" case is when the ciphertext is $$m_1$$ because the adversary knows for sure that in this case $$b=0$$. in all other cases of the ciphertext, this behaves like regular OTP and thus the best the adversary can do is flip a coin. Formally: $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1\mid b=0]=\Pr[c=m_1]+\frac{1}{2}\Pr[c\neq m_1]$$ but $$\Pr[c=m_1]=\Pr[k=m_1\oplus m_0]=\frac{1}{|\mathcal{K}|}$$ so: $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1\mid b=0]=\frac{1}{2}+\frac{1}{2|\mathcal{K}|}$$ the same exact argument can be done when $$b=1$$ so finally: $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1]=\frac{1}{2}+\frac{1}{2|\mathcal{K}|}$$

Is it correct?

Edit:

• define the technical term Priv_{blah}^{bla} that you use. the question is unreadable otherwise. Oct 24, 2021 at 22:01
• @kodlu edited. let me know if there's anything else needed. Oct 25, 2021 at 3:40

No your reasoning is wrong. If I consider an attacker $$\mathcal{A}$$ which output $$0$$ during any execution, we obtain $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1\mid b=0]=1$$. Then your computation $$\Pr[\text{PrivK}_{\mathcal{A},\Pi}^{eav}=1]=\frac{1}{2}+\frac{1}{2|\mathcal{K}|}$$ is wrong.
Hint: Do not cut relatively to $$b$$.