Score:1

One time pad, Proof for a problem

ms flag

We know 2 plaintexts of length L and 2 ciphertexts of length L(we don't know which one belongs which), assuming each given ciphertext is generated by encrypting one of the given plaintexts by XOR'ing (aka exclusive or) with the same key of length L (we don't know the key). Question is asking me to prove that, if the key is uniformly picked from the space defined by the length L, there exists no program that can give the correct key as an output with probability more than ½. I just started to take a cryptography class, and I have many proof questions like this. I can imagine why the probability is ½, but can't formally prove it.

IngIng avatar
ms flag
Sorry i edited question. @kelalaka we use introduction to modern cryptography by Jonathan Katz and Yehuda Lindell but this is not a question from book. Ca you prove it formally or can u give me some clue? Thanks.
Maarten Bodewes avatar
in flag
@Maeher The trick is that you only get to know the values separately, not the plaintext / ciphertext *pairs*. Inging, so how many possible keys are there? Rewrite $M_1 \oplus C_2$!
IngIng avatar
ms flag
@Maarten Bodewes, We have 2 messages which encrypted with same key. $M1⊕C2 = M2⊕C1$, and also $M1⊕C1 = M2⊕C2$. We have 2 equally possible keys. I can see that probability is $1/2$. But how can i formally write this as an answer?
Maarten Bodewes avatar
in flag
NOt sure, I would at least introduce $K'$ and indicate that the probability that $P_1$ is the plaintext of $C_2$is exactly as high as for $C_1$; because of OTP there is no information possible to distinguish the two, as $K$ is fully random.
Titanlord avatar
tl flag
Are you familiar with cryptographic experiments? There is a perfect indistinguishability experiment and for a formal proof you can use that as a basic for computing the probabilities.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.