CSC507/609
University of Miami
19 Jan 2016
Burton Rosenberg

Updated: 10 Feb 2016

Due Date: see assignment.

PROBLEM SET 1
-------------


Given the plaintext, ciphertext and key space {0,1}, the Vernam cipher works as:

	c = k (+) m 

Where the key k must be chosen at random 0 or 1 with probability 1/2 of a 1. That is,
with probability 1/2 the ciphertext equals the plaintext, else the ciphertext is the 
complement of the plaintext.

We suppose there was a eavesdropper that saw the ciphertext, and we are considering all
ways that eavesdropper can conclude with more or less certainty what is the plaintext.

In class we supposed to decision procedures by the eavesdropper: (1) guess always which of
plaintext 0 or 1 is more likely; or (2) guess that the plaintext is equal to the ciphertext.

We showed that it is possible that often (1) is better than (2) - that is ignoring the 
ciphertext is more likely to give a correct answer than basing your answer on the
cipher text.

Note: In these problems, do not assume that the probability distribution on the message
space is uniform. 

1) Suppose the eavesdropper guesses the plaintext by ignoring the ciphertext and
flipping a fair coin, and guessing that the plaintext equals the coin outcome.
What is the probability that the eavesdropper will correctly guess the plaintext.

2) Repeat problem (1) above with a biased coin.

3) In the example in class, what if rather than the eavesdropper guessing the plaintext
is equal to the ciphertext, she guesses that the plaintext is the complement of the 
ciphertext. What is the likelihood of a correct guess?

4) We have calculated the probability of the plaintext being a 0 given that the ciphertext
is a 0, and if it is a 1, using Bayes theorem. This multipart question asks you to 
calculate this from the defintion of conditional probability:

	P(m=0|c=?) = P(m=0 and c=?) / P(c=?)

(a) First identify the probability space. It has 4 outcomes, (m=0,k=0), (m=1,k=0) ....
Give the probably of each outcomes.

(b) What is the set representing events c=0 and c=1; give the probability for each event.

(c) Calculate the conditional probabilities P(m=0|c=0) and P(m=1|c=0).

5) We identified the probability space in question (4) as M cross K. However,
the space might also be described as M cross K cross C. An example element of this
space is (m=0,k=1,c=1). Why can we calculate probabilities correctly in the smaller
space M cross K. (Hint: what is the probability of m=0 and k=1 and c=0 ? )

6) Consider the Vignere cipher of a alphabet of {0,1,2,3,4} (the ciphertext, plaintext
and key all are from this alphabet). The encryption equation is:

	c = m + k mod 5

Assume an infinite key length. That is, for each column of the message a new key k is
chosen independently at random with uniform probability. 

Show this cipher has perfect secrecy. 

7) Suppose the cipher above has a key with key length 5. Show that this 
cipher does not have perfect secrecy.