Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I want solve the next exercise. The author defined the experiment for the cryptosystem $\Pi$, the adversary $A$ and the security parameter $n$ as follows


  1. The adversary $A$ get the input $1^n$ and choose two messages $m^{(0)}$, $m^{(1)} \in M$ with same length;
  2. One key $k \in K$ is generated using $\mathsf{Gen}(1^n)$, and one bit is chosen uniformly at random. Then the message $m^{(b)}$ is encrypted and sent to $A$;
  3. Eventually $A$ outputs b';
  4. If $b=b'$, the experiment result is 1. Otherwise 0.

Definition A cryptosystem $\Pi$ has indistiguishable ciphertexts in the presence of an eavesdropper if for all adversaries $A$ there exist a negligible function $\mathsf{negl}$ such that

$$\Pr[\mathsf{PRIV_{EAV}}(\Pi,A,n)=1]\leq 1/2 + \mathsf{negl}(n).$$

My question: How will I be able to prove that the cryptosystem described below is not secure under the definition above.

Cryptosystem $\Pi$:

  • $\mathsf{Gen}(1^n)$ chooses a bitstring $k \in \{0,1\}^n$ uniformly at random,
  • $\mathsf{Enc}(m,k)$ works as follows: The message $m$ is split into blocks $m_0, m_1, \dots ,m_l$ of $n$ bits. Each block is encrypted separately, as $c_i = m_i \oplus k$. The ciphertext is then the concatenation of the encrypted blocks $c_0, c_1, \dots ,c_l$;
  • $\mathsf{Dec}(c,k)$ is analogous to Enc, but permuting $c$ and $m$.


$K$ is the key space, $M$ the message space and $C$ the ciphertex space

share|improve this question
Why my question have a -1 vote? –  juaninf May 5 '13 at 3:18
What you should do is proposing an attack and estimating its advantage. How does your adversary choose two plaintexts? –  xagawa May 6 '13 at 9:15
add comment

1 Answer

up vote 4 down vote accepted

To prove that a scheme is not secure under such a definition you usually would propose an algorithm such that the experiment described in your question outputs $1$ with probability non-negligibly larger than $1/2$.

As this looks very much like a homework problem I will not give you a solution. However constructing the algorithm is actually very simple in this case. You only need to think about how you would choose the messages $m^{(0)},m^{(1)}$ in such a way that ypu would be able to distinguish their ciphertexts.

As a hint: The deterministic nature of the encryption-process could be a problem here, and you can actually distinguish with probability $1$.

share|improve this answer
Choosing $m_0=m_1$ will never help you. You have to distinguish between the two cases. If the two cases are exactly the same, then they are perfectly indistinguishable for obvious reasons. So no, they have to differ. –  Maeher May 6 '13 at 19:05
I think juaninf may be talking about $m_0$ and $m_1$ as two blocks in one of the plaintexts, in which case he is obviously on a better track. I revised the question to resolve the ambiguity of notation. The two choice messages in the security definition experiment are now $m^{(0)}$ and $m^{(1)}$, while $m_0$, etc refer to blocks of a single plaintext (so one could talk about $m^{(0)}_k$). Maeher: If you like the notation, perhaps consider updating your response? –  Mikero May 6 '13 at 22:25
If there is a choice of $m^{(0)}$ and $m^{(1)}$ that does not allow the adversary to distinguish, then the adversary would be pretty dumb to choose those two messages, wouldn't it? Especially when there are choices it can make that do allow it to distinguish. –  Mikero May 7 '13 at 2:02
@juaninf: $m^{(0)}=m^{(1)}$ is useless, since that guarantees that nobody can distinguish the messages (since they're identical!). Now, $m^{(0)}_0=m^{(0)}_1$, on the other hand... –  Ilmari Karonen May 7 '13 at 5:57
There seems to be some very basic misunderstanding of the experiment here. The adversary is absolutely free in their choice of $m^{(0)},m^{(1)}$. So even if there exists only a single pair that allows you to distinguish, that's fine because you can always choose that pair. Concerning your solution above: It was not the one I had in mind, but assuming that you choose $a,b,c,d$ such that $a \oplus b \neq c \oplus d$ it nevertheless should work. –  Maeher May 7 '13 at 6:25
show 7 more comments

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.