Zero-Knowledge proofs for valid decryption !!

[lcs Mixmaster Remailer]

Some corrections and clarifications:

> Choose another random value t and compute ( g^t * g^r, h^t * h^r * m ),
> for each of m_1, m_2, m_3.  Then publish these values in a random order
> (independent of the random order of the displayed m plaintexts).

Actually this should be a different t for each ciphertext, otherwise g^t
can be figured out and the order revealed.  Also, it should be different
t values for each iteration of the cut and choose.

Although the problem statement assumed you don't know the r exponent for
the ElGamal encryption, maybe in some cases it could be made available,
embedded in the plaintext (typically r can be much smaller than m so
there may be room for it).  Then, decrypting the message would reveal r.

This allows for a greatly simplified cut and choose for the case 1,
where the mapping between the intermediate values and the claimed ElGamal
decryptions must be done.  The prover just reveals t + r mod (p-1) for
each element (this leaks no information about r), and this allows an
easy verification that the intermediate values are ElGamal encryptions
of the claimed plaintexts.  There is no need for the discrete log proof.



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com