Question

1. Consider each of the following encryption scheme and state whether the scheme provides perfect secrecy or not. Justify your answer by giving a detailed proof if your answer is Yes, a counterexample if your answer is No.An encryption scheme whose plaintext space consists of the integers ?={0, 1, ..., 12}and key generation algorithm chooses a uniform key from the key space . Suppose mod 13 and mod 13?={0, 1, ..., 12}????(?)=?+?????(?)=?―?

Answer 1

Enck(m) = m + k Deck(c) = c -k satisfies perfect secrecy

Proof: For any m, m0 ,c ∈ G, we have:

Pr [EncK(m) = c]

= Pr [K + m = c]

= Pr [K = c - m]

Since c-m is a constant value for chosen m and c, we are really considering the probabiltiy that a randomly chosen key is equal to their distance. Since all keys are equally likely and chosen from the key space G, this probabiltiy is equal to:

Since the choice of m was arbitrary, we have that Pr [EncK(m) = c] = Pr [EncK(m0 ) = c],

which is one of the definitions of perfect secrecy.