3
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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], $\endgroup$ – Amanda Mar 26 at 15:09
  • $\begingroup$ @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. $\endgroup$ – Maarten Bodewes Mar 26 at 18:48
  • $\begingroup$ Did you choose the key uniformly? consider AND instead of x-or in the OTP? $\endgroup$ – kelalaka Mar 27 at 8:46
  • 1
    $\begingroup$ The counter-example and follow-up analysis look correct. What is your question? $\endgroup$ – SEJPM Mar 27 at 13:57
0
$\begingroup$

What now follows "My attempt" (added by kelalaka from here) is IMHO a good refutation of the proposition.

The king of proofs is a well-justified counterexample.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.