[freehaven-dev] Re: request for comments on Mixnet Reputations paper

[dmolnar@belegost.mit.edu]

On Tue, 12 Dec 2000, David Wagner wrote:

> > David Wagner wrote:
> > > David A Molnar wrote:
> > > > Suppose I have a message M and a "target" ciphertext C = E_PK(M,r) for
> > > > some randomized public key encryption and padding scheme E_PK with
> > > > padding value r. How difficult is it to find a different M',r' such that
> > > > E_PK(M',r') = C ?
> > >
> > > For El Gamal, it is trivial.  If C = E(M) and C' = E(M'), then
> > > C*C' = E(M*M'), so generate C' = E(1) [a random encryption of "1"],
> > > and then multiply C by C'.
> > 
> > The ciphertext in Elgamal is (g^r, M*g^xr), where r is the random seed
> > and x is the private key. I think David Wagner is talking about the second
> > part of the ciphertext; it is not possible to find a fixed-key collision
> > (i.e. with M' != M) for the whole ciphertext, because that would mean
> > that decryption was ambiguous.
> 
> Sorry.  I just plain misunderstood the original question, so my
> answer should be ignored (if you look at it and try to work out
> the details, you will see that it is bogus, and answers a question
> different from the one asked).

Ok. Understood. Many thanks to you and David H. for pointing this out. 

-David