Zero-Knowledge proofs for valid decryption !!

[Emmanouil Magkos]

There is a list of encrypted messages, published on a bulletin board. Rackel
and only Rackel can decrypt this messages. Encryption is probabilistic, for
instance ElGamal: E(m)=(g^r, h^r  m), where h=g^s with {s} be the private
key of Racel and {r} be a randomness chosen by the sender.

Rackel decrypts E(m_1), E(m_2), E(m_3), and publish the decrypted results in
random order, say (m_2, m_1, m_3). Is there a way for Rackel to prove that
the list of m_i contains only correct open values of the list of E(m_i),
without revealing:

1) the linkage between [E(m_i), m_i]
2) the private decryption key s

(note that she doesn't know the randomness {r})

Does anybody know whether there exists such solution ??.

Thank you in advance, Manos


=====================
Emmanouil Magkos
Department of Informatics
University of Piraeus
185 34 Piraeus, Greece
tel (1): +30 1 2113090
tel (2): +30 1 4142134
fax: +30 1 4142264
mobile: +30 945 075815
e-mail: emagos at unipi.gr
=====================




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