I'm trying to prove that definition 5 and definition 6 in this document are equivalent. This is what I've done at the moment: Asume that the scheme has Indistinguishable encryptions in the presence of an eavesdropper (definition 5), then:

$$\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=1]=\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=0]+\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]=(1/2-\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=1])+\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]\leq 1/2+negl(n)$$

And we get that:

$$\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]-\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=1]\leq negl(n)$$

Now I'm trying to prove that:

$$\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=1]-\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]\leq negl(n)$$

For finishing the inequality with the absolute value. Is there someone who can help me with this? Thanks!

PS: I can understand the last line in the definition 6 in the document I've given: where the probability is taken over...

Can someone explain me that?


1 Answer 1


I've found an answer to my question, I'm going to post it because it can be useful to someone out there.

The point is that, if we assume that $\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=1]\leq 1/2+negl(n)$, then $\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=0]\leq 1/2+negl(n)$ too (if this were not to happen, then we could create an adversary that solves the experiment with a better probability than $1/2+negl(n)$).

This allows us to use the same argument I've used for proving the first inequality for getting the inequality with absolute value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.