Note that the due date falls on the last day of Reading Period. Late submissions can not be accepted without specific authorization from your Residential College Dean.

Instructions Work the problems below, prepare your answers in electronic form, and submit your solutions using the submit script on the Zoo. Remember to specify “7” for the problem number argument to submit. As always, you must properly cite all resources that you use to solve the problems.

Problem 1: Homomorphic Encryption

Consider the Caesar cipher extended to strings. Using the definition of homomorphic encryption given in lecture 22, show whether or not the encryption function E_k is homomorphic with respect to operations ⊙ and ⊙, where ⊙ = ⊙ is:

1. Componentwise addition modulo 26;
2. Componentwise multiplication modulo 26;
3. String concatenation.

In each case, carefully define the message and ciphertext spaces that make sense for the operation, and give a careful definition of the operation. Then argue why E_k is or is not homomorphic with respect to ⊙ and ⊙.

(over)

Problem 2: Anonymous Authentication

Consider the following proof of knowledge that allows Peggy to convince Victor that she knows either the discrete logarithm of y₁ = g^x₁ or the discrete logarithm of y₂ = g^x₂. Assume that Peggy knows x₂. Peggy and Victor execute the following protocol.

	Peggy		Victor
1.	Choose random v1,v2 and w
	Compute t1 = y1wgv1, t2 = y2wgv2
2.			Choose a random c
3.	Calculate c1 = w, c2 = c - c1,
	r1 = v1 and r2 = v2 - x2c2 + x2c1		Check t1y1c1gr1, t2y2c2gr2, c1 + c2c
			Accept if checks succeed.

1. Show that if Peggy and Victor are both honest, then Victor accepts.
2. Assume Polly knows x₁. Describe how Polly can convince Victor that she also knows either x₁ or x₂.
3. Explain why Mallory, who does not know x₁ or x₂, cannot cheat and produce a valid proof.
4. Explain why Victor does not learn which of x₁ or x₂ that Polly knows.