perfectly secret with key chosen uniformly Prove or refute: Every encryption scheme for which the size of the keyspace equals the size of the message space, and for which the key is chosen uniformly from the keyspace, is perfectly secret.
My attempt:
I think the statement is false because I made a counterexample:
$M = \{a, b\}, K = \{k_1, k_2\}, C = \{0, 1\}$. Let $\operatorname{Enc} (k, a) = 0$ and $\operatorname{Enc}(k, b) = 1$ for $k\in\{k_1, k_2\}$. The algorithm will return $a$ in the input ciphertext $0$ and $b$ in the input ciphertext $1$. Clearly, the schema is correct. But if we compare with the rule: $$\Pr [C = c | M = m_0] = \Pr [C = c | M = m_1]$$ We have to : $$\Pr [C = 1∣M = a] = 1 \neq 0 = \Pr [C = 1∣M = b]$$
What now follows &quot;My attempt&quot; (added by kelalaka from here) is IMHO a good refutation of the proposition.
The king of proofs is a well-justified counterexample.