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*?