Re: question about Cramer-Shoup's Cryptosystem

From: Anton Stiglic (stiglic_at_cs.mcgill.ca)
Date: 05/30/03 

Date: Fri, 30 May 2003 11:41:34 -0400

> It is proved that CS is semanticly secure under adaptive chosen ciphertext
attack, while ElGamal is unsecure under adaptive chosen ciphertext attack.
How come?

Think malleability.

While semantically secure (under the DDH assumption), ElGamal is still very
malleable.

Say Alice wants to submit a mid, represented by a number m.

Alice submits her encrypted bid: y^r m % p, g^r % p (where y is the
public key,
p the public prime parameter, g is the generator, r is the random value
chosen
for encryption...)

Oscar wants to underbid Alice by 10%, he can easily manipulate the
ciphertext Alice sent to do so:
     (y^r m % p)* (9/10), g^r % p

The above ciphertext will be decrypted to 9/10 * m.

You can't do this with the CS scheme.

Semantic security is pretty much the most basic notion of security
that exists, see the paper by Bellare, Desay, Pointcheval and Rogaway:
Relations Among Notions of Security for Public-Key Encryption
Schemes.

--Anton