Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 2 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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