Cryptography Question from Katz and Lindell Book Introduction to Modern Cryptogr

Question

Cryptography Question from Katz and Lindell Book Introduction to Modern Cryptography

From Let E = (Gen, Enc, Dec) over message space M be an encryption scheme that achieves perfect secrecy. Let M1 M, M2 =M/M1 be two subsets of M such that |M1| 1, |M2| 1. Furthermore, let D1 be a distribution over M1, D2 be a distribution over M2. Finally, let C1 (resp. C2) be the random variable corresponding to the distribution over ciphertexts when messages are sampled from D1 (resp. D2), and let C1 (resp.C2) be the corresponding ciphertext spaces.

Is it possible that there exists a ciphertext c C1 C2 such that Pr[C1=c] =/= Pr[C2=c]? If yes, give an example of a specific encryption scheme that is perfectly secret and for which the above holds. If not, prove that for any encryption scheme that is perfectly secret, the above cannot hold.

Explanation / Answer

One-Time Pad The one-time pad (OTP) : It operates on bits rather than letters of
the alphabet. If a = a 1 ··· a n and
b = b 1 ··· b n are sequences of bits,
then we write a b to be the sequence
c = c 1 ··· c n dened by c i a i + b i (mod 2).
Note that this is simply the boolean XOR operator,
which we write as . In OTP we have
D = M = C = { 0 , 1 } n . That is, keys, plaintexts,
and ciphertexts are all n -bit strings.
Encryption and decryption are dened as
follows: Enc ( D,m ) = D m Dec ( D,c ) = D c
The scheme satises the correctness requirement because
Dec ( D, Enc ( D,m )) = Dec ( D,D m ) = D ( D m ) = ( D D ) m = m since is an associative operator, and D D = 0 for all D . Like ROT-13, the decryption and encryption operations are the same. Remember, we are starting to require some precision about how exactly the keys are chosen. In OTP, the key is always chosen uniformly at random (from the set of all n -bit strings).

Example: Enc (10110111100 , 10101110010) = 00011001110 .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.