Let $E_k$ be a cipher with a uniform random key $k$ unknown to the adversary. Actually this can be any pseudorandom function family; its invertibility is not relevant in the chosen-plaintext attack model. It might keep state, or it might be randomized; filling in the details of state and/or randomization is left as an exercise for the reader. There are a few different ways to quantify attacks against $E_k$, usually phrased in terms of a random decision algorithm $A(\mathcal O)$ defined on an oracle $\mathcal O$ that may involve $E_k$.
Left-or-right indistinguishability. We define the oracle $\operatorname{LOR}(P_0, P_1) := E_k(P_b)$ where $b$ is a secret fair coin toss unknown to $A$, and the adversary wins if $A(\operatorname{LOR})$ returns $b$.
That is, the adversary will submit a series of message pairs $(P_0, P_1)$, and our oracle always returns the encryption $E_k(P_0)$ of the left message, or the encryption $E_k(P_1)$ of the right message, and the adversary has to figure out which way it is. The left-or-right advantage is $$\operatorname{Adv}^{\operatorname{LOR}}_E(A) := \bigl\lvert\Pr[A(\operatorname{LOR}) = b] - 1/2\bigr\rvert.$$ We measure the distance from $1/2$ because any answer given by $A$ that is independent of the oracle, and therefore of $b$, will always succeed with probability $1/2$; what's interesting is how much better $A$ can do by taking advantage of the oracle.
Real-or-random indistinguishability. We define oracles $\operatorname{Real}(P) := E_k(P)$ and $\operatorname{Rand}(P) := E_k(\tilde P)$, where $\tilde P$ is an independent uniform random message of the same length as $P$, and we will quantify how well the adversary can tell them apart.
That is, the adversary will submit a series of messages $P$ to the oracle, and the oracle might return the ciphertext $E_k(P)$ for each message, or might return the ciphertext $E_k(\tilde P)$ of random gibberish $\tilde P$ of the same length as each message instead. The real-or-random advantage is a measure of how well the adversary can distinguish these two oracles: $$\operatorname{Adv}^{\operatorname{ROR}}_E(A) := \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(\operatorname{Rand})]\bigr\rvert.$$
These two security notions are essentially equivalent, since the best advantage against one is at most double the best advantage against the other, as shown in Bellare–Desai–Jokipii–Rogaway 1997. There are other slightly weaker notions of security, like find-then-guess, which I usually just call IND-CPA, and semantic security, which is equivalent to find-then-guess but usually more of a pain to prove theorems about.
Note that in the left-or-right and real-or-random settings, the adversary is always given real ciphertexts of partially unknown messages. LOR/ROR indistinguishability implies nothing about the shape of ciphertexts—ciphertexts could be written in pig-Latin encoded in KOI8-R, or in Navajo binary, as long as the adversary can't tell two ciphertexts apart.
We can instead consider the difficulty of distinguishing ciphertexts from uniform random bit strings as in Rogaway's CRYPTREC evaluation:
Indistinguishable from uniform random. We define the oracle $F(P) := \tilde C$ where $\tilde C$ is an independent uniform random bit string of the same length as the ciphertext for $P$, and we will quantify how well the adversary can tell $E_k$ apart from $F$.
That is, the adversary will submit a series of messages $P$ and get either the corresponding ciphertext $C = E_k(P)$ each time, or get an independent uniform random bit string each time. The indistinguishability-from-uniform-random advantage is: $$\operatorname{Adv}^{\operatorname{PRF}}_E(A) := \bigl\lvert\Pr[A(E_k)] - \Pr[A(F)]\bigr\rvert.$$ (Called ‘PRF’ here because this is essentially the same notion as for pseudorandom function families. In Rogaway's manuscript, it's called ‘ind\$’ because cryptographers apparently like to mark randomness with \$ signs.)
It is very easy to concoct a cipher that has left-or-right/real-or-random indistinguishability but is trivially distinguishable from uniform random: if $E'_k$ has LOR/ROR indistinguishability, define $E_k(x) = E'_k(x) \mathbin\| 0$ and you get a trivial distinguisher of the ciphertexts from uniform random bit strings, even though $E_k$ obviously still has LOR/ROR indistinguishability. So clearly left-or-right/real-or-random indistinguishability does not imply indistinguishability from uniform random.
How do we show that indistinguishability from uniform random implies left-or-right and real-or-random indistinguishability? Since left-or-right indistinguishability is equivalent to real-or-random indistinguishability, proving the result for ROR implies the result for LOR. We will show that the real-or-random advantage of an adversary to distinguish true ciphertexts from ciphertexts of uniform random plaintexts is at most the sum of
- the adversary's advantage at distinguishing the true ciphertexts from uniform random bit strings, and
- a related adversary's advantage at distinguishing the ciphertexts of uniform random plaintexts from uniform random bit strings.
Let $A$ be a putative real-or-random distinguisher.
Note that the oracle for a real-or-random distinguisher is syntactically like the oracle for a uniform random distinguisher: it takes a plaintext, and it returns a ciphertext-length bit string. So we can just as meaningfully evaluate $A(\operatorname{Real})$ and $A(\operatorname{Rand})$ as in the real-or-random setting, and $A(E_k)$ and $A(F)$ as in the uniform random setting.
By definition, $\operatorname{Real} = E_k$, so $A(\operatorname{Real}) = A(E_k)$.
Note that if $A(\operatorname{Rand})$ submits the plaintexts $P_1, \dots, P_n$ to its oracle, what it gets back are the ciphertexts $E_k(\tilde P_1), \dots, E_k(\tilde P_n)$ where the $\tilde P_i$ are independent uniform random plaintext bit strings. So running $A(\operatorname{Rand})$ is equivalent to running $A'(E_k)$ where $A'(\mathcal O)$ works exactly like $A$ but queries $\mathcal O(\tilde P_1), \dots, \mathcal O(\tilde P_n)$ where $A$ would query $\mathcal O(P_1), \dots, \mathcal O(P_n)$. That is, $A(\operatorname{Rand}) = A'(E_k)$.
Similarly, if $A(F)$ submits the plaintexts $P_1, \dots, P_n$ to its oracle, what it gets back are the ciphertexts $\tilde C_1, \dots, \tilde C_n$ where the $\tilde C_i$ are independent uniform random ciphertext-length bit strings. It could just as well have submitted $\tilde P_1, \dots, \tilde P_n$ to its oracle, as $A'(F)$ would do, since $F$ ignores the input. That is, $A(F) = A'(F)$.
We can combine these facts with the triangle inequality to set the desired bound:
\begin{align*}
\operatorname{Adv}^{\operatorname{ROR}}_E(A)
&= \bigl\lvert\Pr[A(\operatorname{Real})] -
\Pr[A(\operatorname{Rand})]\bigr\rvert \\
&= \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(F)]
+ \Pr[A(F)] - \Pr[A(\operatorname{Rand})]\bigr\rvert \\
&\leq \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(F)]\bigr\rvert
+ \bigl\lvert\Pr[A(F)] - \Pr[A(\operatorname{Rand})]\bigr\rvert \\
&= \bigl\lvert\Pr[A(E_k)] - \Pr[A(F)]\bigr\rvert
+ \bigl\lvert\Pr[A'(F)] - \Pr[A'(E_k)]\bigr\rvert \\
&= \operatorname{Adv}^{\operatorname{PRF}}_E(A)
+ \operatorname{Adv}^{\operatorname{PRF}}_E(A'). \tag*{$\square$}
\end{align*}
