Score:0

One-time pad without zero: proof check

ke flag

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: enter image description here

kodlu avatar
sa flag
define the technical term Priv_{blah}^{bla} that you use. the question is unreadable otherwise.
yankovs avatar
ke flag
@kodlu edited. let me know if there's anything else needed.
Score:1
cn flag

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.

Remember all the intermediates equalities should be true for any adversary

Hint: Do not cut relatively to $b$.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.