# LOR implies unpredictability?

It should be true that classical LOR(Left or Right)-indistinguishability of some mode of operation implies unpredictability. However I've got stuck with the proof of this fact.

LOR-indistinguishability of some mode of operation E means the following: an adversary has access to the oracle, she can query pairs (m1, m2) to the oracle; the oracle would respond by encrypting either left message (m1) or the right one (m2). The mode E is LOR-indistinguishable iff the adversary has hard time to guess whether the left message of the pair was encrypted or the right one.

By unpredictability I mean the following. The adversary is allowed to ask queries of the type M and to obtain the response E(M). The goal is to find a message M*, which was never queried, with the corresponding ciphertext E(M*).

The intuition is that if the adversary A can predict the output of the oracle with "high" probability, then the mode leaks some information, and this adversary can be used to construct LOR-adversary B.

The idea is simple: if we have some oracle (left/right), then we take M (which was asked by A) and we take completely random r with the same length as M, and give this pair (M,r) to our (LOR) oracle. The answer is then goes to A directly.

If A will successively predict the new message, then we bet that the oracle is LEFT, otherwise that it is RIGHT.

In the LEFT universe the probability to predict correctly is the probability of success of A in real-world.

However, I was stuck how to bound the probability of "false positive" in the RIGHT world. The adversary A have some "trash" values E(r) instead of E(M) he was asked for. How much does it helps him to predict E(M*) correctly for some M*?

The reduction will not work. The reason is that any $$E$$ that is LoR indistinguishable has to be randomized. But then, the adversary's output might be different from the outcome of the oracle, even if it evaluates the correct $$x$$ (the one picked by the adversary).
In fact, there is a family of $$E$$'s that is predictable but still LoR indistinguishable. For example consider a public-key encryption scheme that is LoR indistinguishable and let $$E(x)=(\mathit{Enc}(\mathit{pk},x),\mathit{pk})$$. Then also $$E$$ is LoR indistinguishable. However, you can easily find pairs $$(x,E(x))$$ since with one query you can retrieve the public key.
• Adoption to symmetric schemes: Define $E'(m)=E(m)\|E(m\oplus 1^{|m|})$ and have decryption ignore the second half. Then an adversary could present $(m\oplus 1^{|m|},E(m\oplus 1^{|m|})\|E(m\oplus 1^{|m|}))$ with the encryption still being lor-secure. – SEJPM Apr 10 '20 at 8:38
Hmmmm, could you design an artificial $$E$$ that was LOR-unpredictable, but where you could still generate a known $$M^*, E(M^*)$$ pair? Hint: if $$E$$ is nondeterministic, then a query of $$E(M^*)$$ oracle might not give you the same result as the $$E(M^*)$$ value in the known pair.