Description
Problem 1 (CS5158 only, 1 point). Assume we use Shift Cipher, and the message space is M =
{aa, ab, bc}, where Pr[M = aa] = 0.3, Pr[M = ab] = 0.2, Pr[M = bc] = 0.5. In addition, we assume the
key space is K = {0, 1, 2, …, 25} and it is uniformly distributed, i.e., Pr[K = k] = 1/26, for any k ∈ [0, 25].
What is the probability of a ciphertext is XY?
Problem 1 (CS6058 only, 1 point). Assume we have Vigenere Cipher Π = {KeyGen, Enc, Dec}.
Message space is M = {aaaa, faaa}, and the key length could be 1, 2, 3, or 4, and it is uniformly
distributed. In addition, assume an adversary A plays a security game PrivKeav
A,Π as below:
1. A chooses m0 = aaaa and m1 = faaa, and gives m0 and m1 to challenger;
2. Challenger flips a fair coin, gets a bit b, computes cb ← Enck(mb), where k ← KeyGen(·), and returns
ciphertext cb to A.
3. Given cb = cb1cb2cb3cb4, A guesses b
0 = 0 if cb1 = cb2, otherwise it guesses b
0 = 1
4. Outputs 1 if b
0 = b, and 0 otherwise; and we say A wins the game if b
0 = b.
Prove that this adversary can win this game with a probability greater than 1/2.
Problem 2 (1 point). Describe the formal definition of perfect secrecy. Assume each key has θ bits
in a one-time pad, prove this one-time pad is perfectly secure.
Problem 3 (1 point). Although one-time pad is perfectly secure, it has two major assumptions/limitations, which makes it impractical for real applications. Describe the two major limitations of one-time
pad.
Problem 4 (1 point). Compared to an adversary in perfect security, what are the two main differences
for an adversary in computational security?
Problem 5 (1 point). Explain what is a negligible function, and describe the properties of negligible
functions.
Problem 6 (1 point). Describe the details of the security game/experiment for computational security,
and formally explain what is (computationally) indistinguishable.