Security and Cryptography
Electronic Cash, Voting, Auctions, and Watermarking
Due: 16 November 1998
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).
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.
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.
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)
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:
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.
Show how to take the regular ElGamal algorithm and make it (+, x)-homomorphic.