Prove that Definition 2.4 implies Definition 2.1. Definition 2.1: An encryption
ID: 3724900 • Letter: P
Question
Prove that Definition 2.4 implies Definition 2.1. Definition 2.1: An encryption scheme II = (Gen, Enc, Dec) over a message space M is perfectly secret if for every probability distribution over M, every message m e M, and every ciphertext c EC for which Pr[C = c] > 0: Pr[M = mC = c) = Pr[M = m) Definition 2.4: An encryption scheme II = (Gen, Enc, Dec) over a message space M is perfectly secret if for every adversary A it holds that Pr[PrivKXII = 1] = ? Lemma 2.3: An encryption scheme II = (Gen, Enc, Dec) over a message space M is perfectly secret if and only if for every probability distribution over M, every mo, mi e M, and every c E C: Pr[C = CM = mo] = Pr[C = CM = mi] Hint. If a scheme II is not perfectly secret with respect to Definition 2.1, then Lemma 2.3 shows that there exist messages mo, mi e M and c EC for which Pr[C = C|M = mol + Pr[C = CM = mi). Use these me and my to construct an A for which Pr[Privka = 1]> ;.Explanation / Answer
To show that Definition 2.4 implies Definition 2.1
From Definition 2.1, it is clear that the events Pr[M=m] and Pr[C=c] are mutually independant.
That is, if the adversary knows the probability distribution over M; he knows that different messages will be sent.
Now if the adversary observes the cipher text being sent, he should not be able to relate this cipher text seen with his knowledge of probability distribution over M.
In other words, a posteriori likelihood that message M is sent via Cipher text C should be no different that message M should be sent.
This means that underlying cipher text reveals nothing about the message.
From Definition 2.4, PrivKeavA, pi = 1 means A has succeeded.
Probability that A succedded is given as 1/2 => which means A may or may not be successful in decrypting the message over doing a mapping between between known Probability distribution M and cipher text C.
This is expected because from Defintion 2.1, Pr[M=m] and Pr[C=c] are mutually independant and probability of A relating M and C is always 1/2.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.