The problem posed is actually a special case of the problem solved in a paper that was recently accepted at ACM-CCS (Philadelphia, November 2001.) C. Andrew Neff. Verifiable, Secret Shuffles of ElGamal Encrypted Data for Secure Multi-Authority Elections (For various reasons, the title uses the terms "ElGamal" and "Secure Multi-Authority Elections", but the real content of the paper is a solution to a "shuffle problem" which has broader context.) I believe the Dodis, Halevi, Rabin paper mainly cites the work of Abe (M. Abe. Universally Verifiable Mix-net with Verification Work Independent on the number of Mix-centers. EUROCRYPT 98, pp. 437-447, 1998). (Someone please correct me if I am wrong about this.) Another very elegant paper which can provide a solution is R. Cramer, I. Damgaard, and B. Schoenmakers. Profs of partial knowledge and simplified design of witness hiding protocols. Crypto 94, volume 839, Springer-Verlag LNCS, pages 174-187. which tackles a far more general problem -- Boolean combinations of ZK proofs. Both of these results are very important, but from a practical perspective, they have limited use. The main problem is with the overall "proof complexity" -- the data size of the proof, as well as the number of computations required both to construct it and then verify it as a function of the number of elements to be permuted. Secondarily, these are somewhat complicated protocols to implement, and they are at least tricky, if not difficult, to make non-interactive. (The same can be said for other approaches I know based on cut-and-choose.) The technique in the ACM-CCS paper (above) is a surprisingly simple extension of the well known Chaum-Pederson proof of knowledge for the relation $log_g X = log_h Y$. The extension follows fairly easily from the fact that two monic polynomials of degree $k$ over a field $F$ that agree on $k$ points must be identical. We have implemented code in Crypto++ to generate the proof and do the verification. The ACM-CCS paper does not have detailed complexity analysis (that is, $O(n)$ notation is used without explicit calculation of the constant factor), however, this analysis is fairly easy to add. Moreover, emphasis is placed on presentation rather than optimization -- an optimized version can do the proof/verification with a bit more than 1/3 the exponentiations. (The total computation can then be reduced even more by using good crypto numerical techniques.) Further, a paper to appear in Crypto 2001 by Furukawa and Sako will also address this problem. (I know this since they asked permission to cite my work.) They too were motivated to reduce the complexity of the basic mix problem to practical sizes. It is a bit early to do any careful comparisons of the performance of the two approaches since, in any case, the over all difference in performance seems to be small. I am happy to try to answer more detailed questions about the problem and/or the relevant complexity measures. C. Andrew Neff VoteHere, Inc. [EMAIL PROTECTED] -----Original Message----- From: Helger Lipmaa [mailto:[EMAIL PROTECTED]] Sent: Monday, July 09, 2001 6:50 AM To: Emmanouil Magkos Cc: [EMAIL PROTECTED] Subject: Re: Zero-Knowledge proofs for valid decryption !! One reference out of my mind is: * Yevgeniy Dodis, Shaih Halevi and Tal Rabin, "A Cryptographic Solution to a Game Theoretic Problem" , CRYPTO 2000. http://www.toc.lcs.mit.edu/~yevgen/ps/game-abs.html (See Appendix A, esp A.1, and references therein) Helger Lipmaa http://www.tcs.hut.fi/~helger/ On Mon, 9 Jul 2001, Emmanouil Magkos wrote: > 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 ??. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

- Zero-Knowledge proofs for valid decryption !! Emmanouil Magkos
- Re: Zero-Knowledge proofs for valid decryption... Helger Lipmaa
- Re: Zero-Knowledge proofs for valid decryption... lcs Mixmaster Remailer
- Re: FW: Zero-Knowledge proofs for valid decryp... Andy Neff
- Re: FW: Zero-Knowledge proofs for valid decryp... lcs Mixmaster Remailer
- Re: FW: Zero-Knowledge proofs for valid de... Emmanouil Magkos

- Re: Zero-Knowledge proofs for valid decryption... lcs Mixmaster Remailer