CMU 15-827, Homework 2

Out: 17 November 1997

Due: 12 December 1997

Ground rules: You are strongly encouraged to work in groups on this
homework.  I recommend groups of 3-4 people.  If you want to work on
this by yourself, let us know.  Each group should only turn in one
copy of the homework.

You are encouraged to use any sources whatsoever in completing this
homework.  However, please be careful to document any sources that you
use (excluding class lectures, help from the instructors, and material
from the textbook.)

If you have questions about the assignment, please ask Doug Tygar!

(1) Look at several Visa and Mastercard numbers and infer a simple
    algorithm for checking whether a credit card number could be valid.

(2) In electronic commerce, one might want to make a purchase
    anonymously.  One may also wish to complain if one receives poor
    service.  Can you think of some ways to reconcile these properties?
    What additional information is needed from the purchase protocol to
    accomplish this?

(3)  (a)  Here's a simple way to vote -- choose your favorite anonymous
	  electronic cash protocol.  Issue tokens to each voter
	  according to the number of votes they have.  The voters then
	  transfer these tokens to other parties to vote.  Fill out
	  this sketch.  Discuss what works and what doesn't work.  Are
	  there any additional properties not usually in electronic
	  cash protocols that would make them useful for this type of
	  conversion to electronic voting?

     (b)  Can you convert an electronic voting protocol into an
          electronic cash protocol?  Describe how -- or if you can not
          find a way to do it, discuss the difficulties.

     (c)  What about converting between auctions and elections?

(4)  You want to synchronize computers to the real time.  One solution
     is to buy a WWV receiver, or a GPS receiver.  What are the
     security threats with this approach?  (The relevant information
     about WWV and GPS receivers is simply the existence of a time
     signal.)

     Discuss a secure way to synchronize real time at minimum cost and
     minimum human intervention.

(5)  Describe the properties that would be desirable in a secure
     protocol for implementing anonymous auction markets (along the
     lines of NASDAQ or an on-line stock market).

(6)  Pick at least three suggestions given by Needham and Abadi
     in their guidelines for cryptographic protocols.  For each
     suggestions, give an example where their ideas apply and result
     in an improved protocol, and also an example where their ideas
     lead to a poorer protocol.  Extra credit for highly original
     examples.

(7)  Suppose that I want to leak information out of a secure facility
     (for example, the secret plans for Intel's new processor).  Pick
     one of the authentication protocols we've described in class, and
     describe how I can leak information (deliberately) by using the
     authentication protocol.

     Can you describe an authentication protocol that is leak-proof?
     If so, give it; if not, justify why not -- and discuss how you
     can minimize the number of bits leaked.

(8)  Give a "black box" description (not tied to any specific
     cryptographic representation) of Chaum's electronic token
     blinding operation.  Use it to give a black box description of
     Chaum's digital cash protocol