Hybrid Sequence:
The starting point is $\lib{cpa-real}$.
We can apply the security of the PRF in a standard three-hop maneuver:
Sampling $R$ uniformly is indistinguishable from sampling without replacement.
In this hybrid, the $R$ values can never repeat, so the if-statement is always taken. Thus, we can make its body unconditional.
Each value of $\prftable[R]$ is sampled uniformly and used only in a single \xor expression. As a result, $S$ is a OTP encryption of $\ptxt$, with $\prftable[R]$ playing the role of the key.
Finally, we can revert $R$ so that it is sampled uniformly (with replacement). The result is $\lib{cpa-rand}$, which completes the proof.
$\lib{cpa-real}$
$\key \gets \bits^\secpar$
$\cpaenc$($\ptxt$):
// $R\|S \gets \Enc(\key,\ptxt)$
$R $
${}\gets \bits^\secpar$
${}:= \bdaysamp()$
${}\gets \bits^\secpar$
${} \setminus \mathcal{R}$
$$
$Y := {}$
$F(\key,R)$
$\prfquery(R)$
$S $
${}:= {}$
$Y \oplus \ptxt$
$\prftable[R] \oplus \ptxt$
$\otpenc(\ptxt)$
${}\gets \bits^n$
return $R\|S$
$\link$
$\lib{prf-real}$
$\key \gets \bits^\secpar$
$\prfquery$($X$):
return $F(\key,X)$
$\lib{prf-rand}$
$\prfquery$($X$):
if $\prftable[X]$ undefined:
$\prftable[X] \gets \bits^n$
return $\prftable[X]$
$\link$
$\lib{samp-rand}$
$\bdaysamp$( ):
$R \gets \bits^\secpar$
return $R$
$\lib{samp-uniq}$
$\bdaysamp$( ):
$R \gets \bits^\secpar \setminus \mathcal{R}$
$\mathcal{R} := \mathcal{R} \cup \{ R \}$
return $R$
$\link$
$\lib{otp-real}$
$\otpenc$($\ptxt$):
$\key \gets \bits^n$
$\ctxt := \key \oplus \ptxt$
return $\ctxt$
$\lib{otp-rand}$
$\otpenc$($\ptxt$):
$R \gets \bits^n$
return $R$