0
$\begingroup$

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

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

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

$\endgroup$

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.