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

[David Wagner <daw@cs.berkeley.edu>]

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

-- David