Can you help me understand indistinguishably as described in the CPA security definition?

Question

When I read the definition of the CPA indistinguishably encryption scheme, I see that the adversary can use an oracle as many times (to get as many encryptions of any messages it choose). An the end of the experiment, it has to distinguish between two messages $m_0$ and $m_1$ while it gets $c_b$ (from some challenger), which may be one of $m_0$ and $m_1$ encryptions.

But what if the adversary uses the oracle to get the encryptions (of $m_0$ and $m_1$)? Does that mean the encryption algorithm uses some probabilistic way and generates an exponential ciphertext space for every key, which does not give the adversary a polynomial advantage?

Answer 1

Yes, your intuition is completely right (assuming a polynomial-time adversary and a super-polynomial message space, which is the usual setting). If the scheme were deterministic, then the adversary could simply use the oracle to distinguish which message was encrypted. Therefore, no deterministic encryption can be CPA-secure. This is a well-known implication of the definition of CPA-security.