Suppose a common message ($M$) is XOR'ed with two different keys $K_1,K_2$ producing two ciphertexts $C_1,C_2$. Thus,

$$M \oplus K_1 = C_1\\ M \oplus K_2 = C_2$$

On observing $C_1$ and $C_2$, an adversary can obtain the value of $C_1 \oplus C_2 = K_1 \oplus K_2$. Is this scheme semantically secure? Note that $|K_1|=|K_2|=|M|$ and the keys are randomly chosen from a uniformly distributed large key space ($\approx 2^{255}$).

  • $\begingroup$ In the OTP, what is the aim ? Hide the key or hide the message ? Also remember that the key are uniformly distributed. $\endgroup$
    – Biv
    Commented May 9, 2016 at 13:28
  • $\begingroup$ Is $|M| = 255 bits$? $\endgroup$ Commented May 9, 2016 at 13:31
  • $\begingroup$ @Biv The aim is to determine whether $C1$ and $C2$ gives any extra information about $M$. Thus is- $E(M|C1,C2)=E(M)$\\ $K_1$ and $K_2$ are two different keys which have same length of that of $M$ and are chosen randomly from a uniformly distributed key space. $\endgroup$ Commented May 9, 2016 at 13:32
  • $\begingroup$ @HenrickHellström: yes $|M| = 255 bits$ $\endgroup$ Commented May 9, 2016 at 13:35
  • $\begingroup$ @DebanjanSadhya then I would advise you to, simplify your scheme: consider that $M$ is only 1 bit long, idem for $C$ and $K$. What is the probability that $K_1 = 1$, that $K_1 = 0$ idem for $K_2$. Then add $M$ in the mix. What pieces of information did you gain ? What pieces of information do you want to gain ? Try a case study. $\endgroup$
    – Biv
    Commented May 9, 2016 at 13:47

1 Answer 1


As long as the keys $K_i$ are only used once, this is semantically secure. To see it, observe that if $K_i$ is a uniformly random value in $\{0,1\}^{|M|}$ then so is $C_i = M \oplus K_i$.


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.