- Need Proof For Statement In Part B 1 (166.68 KiB) Viewed 25 times
Need proof for statement in part B.
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
Need proof for statement in part B.
Need proof for statement in part B.
2. Perfect Secrecy. Suppose P and C are sets of, respectively, plaintext and cipher- text symbols. We consider the sets Pn of (respectively Cn) the collection of length n messages (respectively encrypted messages by keys from K) with plaintext from P (respectively from C). We think on Pn, and Cn, as random variables, i.e., they are equipped with probability distributions. Denote by K a set of keys k for encryptions ek: Pn → Cn, and decryptions dk : Cn + Pn. Remember that K is a random variable and equipped with a probability distribution, and that: (i) Pn and K are independent. (ii) Pn and K determine Cn. (iii) Cn and K determine Pn. Let us denote elements of Pn by a = a1...An, and of Cn by b = b[...bn. (a) Recall that we say that the system (Pn, Cn, K, {ek, dk; k E K}) ( (3) has perfect secrecy if Pn and Cn are independent, i.e., prob(x = a, y = b) = prob(x = a) · prob(y = b), . = for every a e Pn, and b E Cn. (b) Suppose, for simplicity, that Alice might use every message from Pn (i.e., every message is likely to appear with positive probability). Show that, if (3) has perfect secrecy then, we have #(Pn) < #(K).
2. Perfect Secrecy. Suppose P and C are sets of, respectively, plaintext and cipher- text symbols. We consider the sets Pn of (respectively Cn) the collection of length n messages (respectively encrypted messages by keys from K) with plaintext from P (respectively from C). We think on Pn, and Cn, as random variables, i.e., they are equipped with probability distributions. Denote by K a set of keys k for encryptions ek: Pn → Cn, and decryptions dk : Cn + Pn. Remember that K is a random variable and equipped with a probability distribution, and that: (i) Pn and K are independent. (ii) Pn and K determine Cn. (iii) Cn and K determine Pn. Let us denote elements of Pn by a = a1...An, and of Cn by b = b[...bn. (a) Recall that we say that the system (Pn, Cn, K, {ek, dk; k E K}) ( (3) has perfect secrecy if Pn and Cn are independent, i.e., prob(x = a, y = b) = prob(x = a) · prob(y = b), . = for every a e Pn, and b E Cn. (b) Suppose, for simplicity, that Alice might use every message from Pn (i.e., every message is likely to appear with positive probability). Show that, if (3) has perfect secrecy then, we have #(Pn) < #(K).
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!