Score:4

Unable to understand notation regarding Shannon's theorem

cn flag

the following equation is used to prove the Shannon's theorem by showing the existence of two messages $m_0, m_1$ if $|K| < |M|$ but I'm unable to visualize/understand the probabilities. Especially the $Pr$ over $K$ thing doesn't get into my head. Anyone able to explain it?

  • $\mathcal{K}$ is the keyspace
  • $\text{Pr}$ means probability
  • $m_0$ and $m_1$ are messages from the message space $M$
  • $c$ is the ciphertext
  • $K$ is a random variable determining the key
  • $\text{Enc}(k, m)$ is the encryption algorithm

Then: $\underset{\mathcal{K}}{\text{Pr}}[\text{Enc}(K, m_0) = c] \neq \underset{\mathcal{K}}{\text{Pr}}[\text{Enc}(K, m_1) = c]$

Daniel S avatar
ru flag
Welcome to CryptoSE. I might paraphrase this as “The number of keys that would encrypt $m_0$ as $c$ is not the same as the number of keys that would encrypt $m_1$ as $c$”. This is not quite fully precise, but close.
fgrieu avatar
ng flag
A definition of (discrete) probability may help. $\underset{\mathcal K}\Pr[K\text{ smurfs}]$ is defined as the ratio of: the number of elements $K$ in set $\mathcal K$ such that $K\text{ smurfs}$, over the number of elements in set $\mathcal K$. This ratio is thus a rational in range $[0,1]$.
Score:6
ru flag

$\underset{\mathcal{K}}{\text{Pr}}[\text{Enc}(K, m_0) = c]$ (and similarly $\underset{\mathcal{K}}{\text{Pr}}[\text{Enc}(K, m_1) = c]$) means the probability that $\text{Enc}(k, m_0) = c$, where you choose the key $k\in \mathcal{K}$ at random. Notice that, here, the values $m_0$ and $c$ are fixed, so what we want to know is, for these fixed $m_0$ and $c$, what is the probability that a uniformly random key $k$ results in encrypting $m_0$ to $c$.

As @fgrieu pointed out in the comments, the probability of a discrete event is simply the number of "favorable" cases divided by the total number of cases, so here it would be

$$\underset{\mathcal{K}}{\text{Pr}}[\text{Enc}(K, m_0) = c] = \frac{|\{k\in\mathcal{K} : \text{Enc}(k, m_0) = c\}|}{|\mathcal{K}|}.$$


PS: Sometimes we also add the randomness of the encryption algorithm into the equation. This is not that relevant for this discussion, but what this means is that you consider an encryption algorithm of the form $\text{Enc}(k, m, r)$, where $r\in\{0,1\}^\ell$ (for some $\ell$) is chosen uniformly random. Then you simply add $r$ as a subscript in the probability.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.