CMU 15-827

Security and Cryptography

Fall 1998
 
 

Electronic Cash, Voting, Auctions, and Watermarking

  
 

Wing

Homework 4

Due: 16 November 1998
  1. E-cash, voting, and auctions [30 points]

    1. 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 he/she has. The voters then transfer these tokens to other parties to vote. Fill out this sketch. Discuss what works and what does not work. Are there any additional properties not usually in e-cash protocols that would make them useful for this type of conversion to electronic voting?

    2. Can you convert an electronic voting protocol into an electronic cash protocol? Describe how, or if you cannot, discuss the difficulties.

    3. Can you convert between auctions and elections? Describe the conversions both ways, or if you cannot, discuss the difficulties.

  2. Anonymous auctions [15 points]

    3. 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).

  3. Fingerprinting and Steganography [15 points]

    4. One of the drawbacks of using cryptography to protect privacy in communications is that although encrypted messages will not be understood they may look suspicious and attract attention because they look unintelligible.

    Steganography is the technique that allows you to send a secret message embedded into a large message that may look completely normal to an adversary. As we’ve seen through digital watermarking, for example, Alice can send an encoded picture of her dog to Bob and change all the low order bits of each pixel in order to encode a message. An eavesdropper, Eve, just thinks Alice is showing a picture of her dog to Bob.

    Stegnography and fingerprinting thus have something in common. Both techniques embed a "message" in a larger object in a way that the larger object’s functionality is not compromised.

    Comment on the similarities and differences in goals between the two techniques. Also comment how the differences would influence the design of a steganographic scheme versus a fingerprinting scheme.

  4. Counterfeit Original Attack [20 points]

    In Craver et al. it was shown that if an invertible watermark embedding function is used, an attack called the counterfeit original becomes possible. The figure below shows how the attack works.

    Alice would like to protect her original image I. She uses the invertible watermark embedding algorithm Y to hide the copyright information CA with the secret key SA in the original image and obtains the watermarked image I'. Formally, Alice computes Y ( I, CA, SA ) = I'.Mallory is also rather fond of image I and would like to embed his own copyright message in the image to sell it himself. Because the embedding function is invertible, Mallory creates his copyright message CM and computes the counterfeit original I' obtained by evaluating Y-1 ( I', CM, SM ) = I'. The image I' also looks as if it contains Alice's watermark. Alice claims that I is the original image and Mallory explains that the true original is I'.

    There's one more detail worth mentioning: In some cases, Alice's original I looks as if it contains Mallory's watermark, which is an annoying property of this attack. It is clear that Mallory's fake original I' contains Alice's watermark, but in the other direction it is counter intuitive.

    Give two different ways to prevent a counterfeit original attack.

  5. Blinding with ElGamal [20 points]

    6. In class we saw a way to blind messages for signatures using RSA. In this problem we ask you to construct blind signatures for a variation of the ElGamal signature scheme.

    The ElGamal signature we will consider is as follows. Let p be a large prime, g a generator, x the secret key of the Bank and y = gx the corresponding public key. Let H be a collision-free hash function (as MD5 for example).

    When the Bank wants to sign a message m she computes

    a = gk mod p

    for a random k and

    c = H(m,a)

    and finally

    b = kc + xa mod (p-1)

    The signature of the message m is sig(m) = (a,b). Given the triple (m,a,b) the verification is performed by computing c = H(m,a) and checking that

    gb = acya

    So the withdrawal protocol could be as follows:

    1. The Customer tells the bank she wants a $1 coin.
    2. The Bank replies with 100 values ai = gki for random ki
    3. The Customer sends back ci = H(mi,ai) where mi are all $1 coins.
    4. The Bank asks the user to open 99 of those.
    5. The Customer reveals 99 of the mi’s.
    6. The Bank replies with bi = kici + xai mod(p-1) for the unopened index i

    However this is not anonymous since the Bank can recognize the Customer when they come back. In order to make them really anonymous, the Customer has to change the value of "challenge" ci computed at step 3. This modification will allow her to compute a different signature on mi on her own which will not be recognizable to the Bank when the coin comes back. A possible way to do this is for the Customer to "behave" as if the ai’s are equal to gki+a i where the a i ‘s are values that she knows. Show how to modify the above protocol to make it anonymous.

    During the protocol the Bank will check as usual that this modification has been performed correctly by asking the Customer to open 99 random blindings.

  6. Extra Credit (Optional) [10 points]

    7. Show how to take the regular ElGamal algorithm and make it (+, x)-homomorphic.