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 reading the proof of the implication "Def 2.1 $\Rightarrow$ Def 2.4" in these slides about Adversarial Indistinguishability and Perfectly-Secret Encryption. I have a doubt in the slide 10. Here it says:

Construct an adversary $A$ who outputs $m_0$, $m_1$ in the first step of $\mathsf{PRIV_{EAV}}(\Pi,A,n)$. Then if $A$ receives any ciphertext $c' \neq \tilde{c}$ it outputs a random bit $b_0$; if it receives the ciphertext $\tilde{c}$, it outputs $b_0 = 0$.

How is $A$ able to "receive any ciphertext $c'$". Perhaps the adversary not receives only the ciphertext $Enc(m_b)$?

share|improve this question
Why I have vote -1? – juaninf May 20 '13 at 13:52
up vote 2 down vote accepted

The adversary $\mathcal A$ is an entity (think of a computer program) designed to participate in the experiment $\operatorname{PrivK}^{\text{eav}}_{A,\Pi}$.

So the adversary produces two messages, then is given the encryption of one of them, and has to guess which one it was.

Of course, you can give the adversary other "ciphertexts" too, but this wouldn't be the same experiment, and the results of this thus don't matter for the experiment (they might be interesting in other experiments, though).

The proof does only have to consider the behavior of the adversary in the experiment, not in other cases.

share|improve this answer
understand, I found here… (in the last page) other proof for the same implication I cann't understand Why $$Pr[\mathsf{PRIV_{EAV}}(\Pi,A,n)=1] = \dfrac{1}{2}\[Pr[A(c)=B|B=0] + Pr[A(c)=B|B=1]\] = \dfrac{1}{2}\[Pr[A(c)=0|B=0] + \dfrac{1}{2}Pr[A(c)=1|B=1]\]$$ – juaninf May 20 '13 at 13:52

This is part of how the notion of security is defined. In the definition, the adversary is an algorithm that produces a pair of messages, and then gets back (in return) a ciphertext. The adversary is then supposed to do something (predict whether the ciphertext is the encryption of the first message or the second message), but that's not relevant -- what is relevant is that this algorithm receives a ciphertext from its oracle immediately after selecting a pair of messages.

If you like, you can think of this as a game, with a referee, an adversary, and an oracle. The adversary selects a pair of messages somehow and sends them to the oracle. The oracle responds by sending a ciphertext back to the adversary. The adversary receives this ciphertext, does some computation, and then outputs a bit. We define the condition under which the adversary wins, and under which the adversary loses. I won't go into the details of that condition; for the purposes of your question, all I need point out is that this game involves the adversary receiving a ciphertext from its oracle at a certain point in the game. That's the "receive" part you were asking about.

This should be explained in any textbook or good course on theoretical cryptography.

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.