Question

Assume we require only that an encryption scheme (Gen, Enc, Dec) with message space M satisfy the following: For all m ∈ M, we have
Pr[DecK(EncK(m)) = m] ≥ 2−t. (This probability is taken over choice of the key as well as any randomness used during encryption.) Show
that perfect secrecy can be achieved with |K| < |M| when t ≥ 1. Prove a lower bound on the size of K in terms of t.

Answer 1

Solution:

Let K ={0;1}ⁿ and M={0;1}^n+t. The algorithm chooses a string from K. To encrypt a message m∈M using key k, let m' denote the first n-bits of m and output c:=m'⊕k(both m' and k have length n). To decrypt a ciphertext c using key k, choose a random string r←{0; 1}ⁿ and output m:=(c⊕k)||r. Since from given Pr[Deck(Enck(m)) =m] = 2^-t that decryption is correct if and only if the random string r chosen during decryption happens to equal with the last t bits of m.Perfect secrecy of this scheme follows from the proof of the one-time pad .Lower bound:|K|≥|M|·2^-t.