CPSC 467b: Cryptography and Computer SecurityHandout #10
Professor M. J. Fischer   April 19, 2013


Problem Set 7

Due on Wednesday, May 1, 2013.

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 Ek is homomorphic with respect to operations M and C, where M = C 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 Ek is or is not homomorphic with respect to M and C.


Problem 2: Anonymous Authentication

Consider the following proof of knowledge that allows Peggy to convince Victor that she knows either the discrete logarithm of y1 = gx1 or the discrete logarithm of y2 = gx2. Assume that Peggy knows x2. Peggy and Victor execute the following protocol.

Peggy Victor

1.Choose random v1,v2 and w
Compute t1 = y1wgv1, t2 = y2wgv2 t1,t2
- →
2. ← c- Choose a random c
3.Calculate c1 = w, c2 = c - c1,
r1 = v1 and r2 = v2 - x2c2 + x2c1c1,c-2,r→1,r2Check t1=?y1c1gr1, t2=?y2c2gr2, c1 + c2=?c
Accept if checks succeed.

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