In "Introduction to Modern Cryptography" by Jonathan Katz exercise 2.6 goes like this: "Say encryption scheme (Gen, Enc, Dec) satisfies DEFINITION 2.1 for all distributions over ℳ that assign non-zero probability to each m ∈ ℳ (as per the simplifying convention used in this chapter). Show that the scheme satisfies the definition for all distributions over ℳ (i.e., including those that assign zero probability to some messages in ℳ). Conclude that the scheme is also perfectly secret for any message space ℳ' ⊂ ℳ.".

DEFINITION 2.1 states that:

An encryption scheme (Gen, Enc, Dec) over a message space ℳ is perfectly secret if for every probability distribution over ℳ, every message m ∈ ℳ, and every ciphertext c ∈ 𝒞 for which Pr[C = c] > 0: P[M=m | C=c] = P[M=m]

The "Hint" that is given at the end of the problem statement is what is detrimental to my underlying judgement of an otherwise trivial, intuitive problem. The problem is apparently solvable using Shannon's Theorem, given here as a statement for encryption schemes where |𝒞|=|ℳ|=|𝒦|.

Now, given this is a general setting, I cannot reduce this problem to a case in which the size of these sets coincide to apply the statement of the Theorem, neither by expanding ℳ or getting rid of some keys in 𝒦.

I managed to prove that $P[M=m | C=c] = P[M = m] = 0$ for the appropriate messages that are impossible.


Your Answer

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

Browse other questions tagged or ask your own question.