I am reading papers about homomorphic encryption recently. To my knowledge, all of them opts for the Left-or-Right security i.e. distinguish between $M_0$ and $M_1$ given $\mathcal{E}_K(M_b)$ for $b \gets \{0,1\}$. So my question is:
Can Homomorphic Encryption achieves indistinguishability from random bits?
More generally, can public-key encryption with homomorphism achieves IND$-CPA?
Often in homomorphic encryption, what "stage" you are at in the computation is leaked (intentionally) by the format of the ciphertext. As a very simple example, many FHE schemes have a "ciphertext modulus" $q$ associated with them. This ciphertext modulus is often written as some chain $q_0 := q, q_1 := q/\Delta,\dots, q_k := q/\Delta^k$ of moduli, where one has ciphertext $q_i$ after the $i$th multiplication. For such schemes, the ciphertexts are mutually-distinguishable across different levels of the computation, so are distinguishable from random bits.
So, to get a cryptosystem of the form you want, you would have to use FHE without the above structure. Such schemes exist (for example FHEW / TFHE / FINAL), though they only compute homomorphic computations with small precision (think $\approx 8$ bit functions). They do this very efficiently though. Such schemes probably already satisfy your desired definition. If they don't, they should be able to be made to at essentially no cost by adding an encryption of 0 after homomorphic evaluations.
Yes. Consider the GSW-levelled homomorphic encryption scheme. A pseudorandom matrix $A \leftarrow \mathbb{Z}_q^{n \times m}$ serves as the scheme's public key, while the secret key is a vector $s \leftarrow \mathbb{Z}_q^n$. To encrypt a bit $b \in \{0,1\}^n$, the encryption algorithm randomly selects a matrix $R \leftarrow \{0,1\}^{m \times N}$ and outputs a ciphertext $c = b\cdot G + AR$, where $G$ is the gadget matrix. According to Lemma 7 on page 26 of Halevi's tutorial, the ciphertext is pseudorandom. The proof is essentially using the fact that if $A$ was a truly random matrix, then $AR$ is random (even in the presence of $A$) due to Leftover Hash Lemma.
