Throughout this section, we assume that a cryptosystem \((\setMessages , \setCryptograms , \setKeys , \setEncryptions , \setDecryptions)\) is specified, and a particular key \(k \in \setKeys\) is used for only one encryption. Let us suppose that there is a probability distribution on the plaintext space, \(\setMessages\) . Thus the plaintext element defines a random variable, denoted \(\randomVariable{m}\). We denote the a priori probability that plaintext \(m\) occurs by \(\Probability[\randomVariable{m} = m ]\). We also assume that the key \(k\) is chosen (by \(\Alice\) and \(\Bob\)) using some fixed probability distribution (often a key is chosen at random, so all keys will be equiprobable, but this need not be the case). So the key also defines a random variable, which we denote by \(\randomVariable{k}\). Denote the probability that key \(k\) is chosen by \(\Probability[\randomVariable{k} = k]\). Recall that the key is chosen before Alice knows what the plaintext will be. Hence, we make the reasonable assumption that the key and the plaintext are independent random variables.

The two probability distributions on \(\setCryptograms\) and \(\setKeys\) induce a probability distribution on \(\setCryptograms\) . Thus, we can also consider the ciphertext element to be a random variable, say \(\randomVariable{c}\). It is not hard to compute the probability \(\Probability[\randomVariable{c} = c]\) that \(c\) is the ciphertext that is transmitted. For a key \(k\in\setKeys\), define

\[\function{C}(k) = \{e_{k}(m) :\forall m \in\setMessages\}.\]

That is, \(\function{C}(k)\) represents the set of possible ciphertexts if \(k\) is the key. Then, for every \(c \in \setCryptograms\) , we have that \(\Probability[\randomVariable{k} = k] = \sum_{k:c\in\function{C}(k)}^{123}{\Probability[\randomVariable{k} = k]\Probability[\randomVariable{c} = k]}\) ∑ Pr [ K = K ] Pr [ x = d K ( y )] . { K:y ∈ C ( K )}