# 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]$$

• I think the statement is false because I made a counterexample: M = {a, b}, K = {k1, k2}, C = {0, 1}. Let Enc (k, a) = 0 and Enc (k, b) = 1 for k = k1, k2. 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 = m0] = Pr [C = c | M = m1] We have to : Pr [C = 1∣M = a] = 1 ≠ 0 = Pr [C = 1∣M = b], Mar 26, 2021 at 15:09
• @Amanda If you edit that into the answer it may gain some hints, as it currently sits at -2 due to the time between asking and answering the comment. Mar 26, 2021 at 18:48
• Did you choose the key uniformly? consider AND instead of x-or in the OTP? Mar 27, 2021 at 8:46
• The counter-example and follow-up analysis look correct. What is your question? Mar 27, 2021 at 13:57