YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 467b: Cryptography and Computer Security | Handout #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 E_{k} is homomorphic with respect to operations
⊙_{} and ⊙_{}, where ⊙_{} = ⊙_{} is:

- Componentwise addition modulo 26;
- Componentwise multiplication modulo 26;
- 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_{1} = g^{x1} or the discrete logarithm of y_{2} = g^{x2}. Assume that Peggy knows x_{2}.
Peggy and Victor execute the following protocol.

Peggy | Victor | ||

1. | Choose random v_{1},v_{2} and w | ||

Compute t_{1} = y_{1}^{w}g^{v1}, t_{2} = y_{2}^{w}g^{v2} | |||

2. | Choose a random c | ||

3. | Calculate c_{1} = w, c_{2} = c - c_{1}, | ||

r_{1} = v_{1} and r_{2} = v_{2} - x_{2}c_{2} + x_{2}c_{1} | Check t_{1}y_{1}^{c1}g^{r1}, t_{2}y_{2}^{c2}g^{r2}, c_{1} + c_{2}c |
||

Accept if checks succeed. | |||

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