# Shannon cipher with fewer keys than messages

Alice and Bob have a set $\mathcal{M}$ of $|\mathcal{M}|$ messages and a set $\mathcal{K}$ of $|\mathcal{K}|$ keys. Alice wants to send a message $m \in \mathcal{M}$ to Bob. She uniformly picks a key $k \in \mathcal{K}$ and encodes the message $m$ with it to create $x = e(m,k)$ (She uses different keys for different messages as much as possible). Bob knows the encoding and uses the key $k \in \mathcal{K}$ to decode $m$ as $m=d(x,k)$. If $|\mathcal{K}| \ge |\mathcal{M}|$ perfect secrecy is achievable and the best strategy for Eve who only knows $|\mathcal{M}|$ will be simple guessing. If $1 \le |\mathcal{K}| < |\mathcal{M}|$, then some keys are used multiple times and there is some information leakage to Eve. What is the best (maximum likelihood) decoding strategy (algorithm) for Eve assuming that she knows the encoding and decoding strategies? I appreciate any comments or if you can direct me to a good reference on this.

• Just enumerate all keys, compute the corresponding messages and then check which messages were never output? Eve is a computationally unbounded goddess after all. – CodesInChaos Mar 2 '17 at 9:04
• How does Bob know which key Alice used? – Christian Matt Mar 5 '17 at 14:56
• We assume that the message-key mapping in known to Bob. – Mohsen Kiskani Mar 5 '17 at 19:33
• What do you mean by "message-key mapping"? Your question states that Alice chooses the key uniformly from the set of all keys. – Christian Matt Mar 6 '17 at 0:24
• That's true but we assume that Alice's choice of the key for a message is known to Bob. – Mohsen Kiskani Mar 6 '17 at 17:31