For a fixed encryption scheme, denote the encryption method (in the sense of computer science) by $E:\mathcal M\to\mathcal C$, and the decryption method by $D:\mathcal C\to\mathcal M$. Here, $\mathcal M$ denotes the plaintext space, and $\mathcal C$ denotes the ciphertext space. Encrypting a message $m\in\mathcal M$ means calling the method $E$ to obtain $E(m)$.
In the eyes of a computer scientist, this all makes sense. However, mathematically speaking, the encryption method $E:\mathcal M\to\mathcal C$ is not actually a map: the output may depend on some random choice that was made when calling the method $E$.
To put it in a very provocative way, for $m_1,m_2\in\mathcal M$, we may have: $$m_1=m_2\quad\text{and}\quad E(m_1)\neq E(m_2).$$
Any mathematician would agree that already writing down something like "the encryption method is $E:\mathcal M\to\mathcal C$" is objectionable and should be avoided.
I would like to know: What ways are there to fix this? My goal is to find a mathematically sound way of treating the encryption method $E$, while still keeping the notation easy to understand.
Presumably there is some set $\mathcal R$ of possible random choices, and then $E$ would be a function from $\mathcal M\times\mathcal R$ to $\mathcal C$.