Not only can encryption schemes have randomness, but in some cases (e.g., public-key encryption), they must be randomized. This is not a problem since we require an encryption scheme to be correct, that is, for any message $m$ and any key $k$ it holds that
$$\Pr \big[\ \text{DEC} \left( \ \text{ENC}\left(k, m, R\right) \ \big) = m \right] =1$$
over the randomness $R$.
The reason that public key schemes must be random stems from the way we define security: we don't wish the ciphertext to leak any information about the encrypted message. The classical example is the following. Assume that $(pk,sk)$ is the public and secret key, respectively, and that the adversary intercepts an encrypted message $c$ sent to some unit in the field. The adversary knows that the message is either "ATTACK " or "RETREAT", but doesn't know which. One thing that the adversary can do is to encrypt both messages using the public $pk$. let $c_A = \text{ENC}_{pk}(\text{"ATTACK "})$ and $c_R = \text{ENC}_{pk}(\text{"RETREAT"})$. If $\text{ENC}$ is deterministic, the adversary can find out the message with certainty by comparing $c$ to $c_A$ and $c_R$.
The way this notion is formally defined is known as semantic security:
An encryption scheme is semantically secure if any adversary ${\cal A}$ cannot win the following game with probability noticeably greater than $1/2$:
- A challenger ${\cal C}$ generates keys $(pk,sk)$ and sends the public key $pk$ to the adversary.
- ${\cal A}$ chooses two messages of equal length $m_0$ and $m_1$ and gives them both to ${\cal C}$.
- ${\cal C}$ uniformly picks a bit $b\in\{0,1\}$ and sends back $\text{ENC}(m_b)$.
- ${\cal A}$ needs to say which message was encrypted: $m_0$ or $m_1$, that is, he needs to output the bit $b$.
(I'm omitting the security parameter $\kappa$, which is critical for defining "negligible" or "noticable"; We need to assume that the generation of the keys depends on $\kappa$, and that the advantage ${\cal A}$ has above $1/2$ is negligible in $\kappa$, i.e., less than $\kappa^{-\omega(1)}$)