### Re: FW: Zero-Knowledge proofs for valid decryption !!

Andy Neff writes: > 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 Do you use cut and choose with an intermediate permutation, showing that it either maps to the one or to the other? Cut and choose in this way goes back to the very earliest work on ZK proofs; it is the classic way to show in ZK that two graphs are identical. > 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.) Interesting point, that this problem arises very naturally in the case of mix-nets. They want to prove that they are operating correctly so want to show that their outputs are the decryptions of their inputs without revealing the correspondence. Probably that's what motivated the problem from the questioner? Note to people asking questions, as payment for the hard work of your responders you should give some background about why your question is interesting. > 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. I guess in this case, you'd have say (A, B, C) mapping to (1, 2, 3) and you'd prove something like: (A->1 OR A->2 OR A->3) AND (B->1 OR B->2 OR B->3) AND (C->1 OR C->2 OR C->3) This could be faster than cut and choose for small permutations, depending on the security factor. Unlike cut and choose the size of the proof does not depend on the security parameter. > 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.) It seems that with cut and choose, the size of the proof is linear in the number of texts being permuted, and linear in the security factor. So that does not sound too bad, although of course if you have thousands of texts then it could get out of hand. An interesting point with regard to the security parameter when dealing with the Schnorr heuristic to make them non-interactive: Often the security parameter can be much lower in an interactive proof than in the non-interactive form. In an interactive proof you will probably be happy with a security parameter of 20 bits, corresponding to 1 chance in a million of successful cheating by the prover. Or even 10 bits for 1 chance in a thousand may be acceptable if the punishment for cheating is significant. Few cheaters would try it if they have a .999 chance of being caught and punished. However when we turn these into non-interactive proofs using the Schnorr heuristic (pre-commit to all values, hash them and use that to produce the challenge bits), the equation changes. Instead of probability of being caught, the security parameter now represents the work necessary to find a hash value that lets you cheat. A security parameter of 10 means the server needs to try 1024 times on the average to find a set of values that satisfy the proof even though he is cheating. A parameter of 20 means that the server needs to try a million values to find some that work. If the protocol is acceptably efficient in one iteration, iterating it a thousand or even a million times may well be an acceptable cost for a server if that allows it to cheat undetectably. So when using non-interactive proofs, verifiers probably will demand security parameters of at least 40, 60 or even 80 bits. This makes the proofs correspondingly more expensive. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: FW: Zero-Knowledge proofs for valid decryption !!

The background of my question was an auction application where encrypted bids are published on a bulletin board. All bids are authenticated, i.e. signed by the bidders. Since there is no anonymity, (there are reasons for this), the link between the encrypted bids and the decrypted results, which will be published for verifiability, must be hidden. Note that in electronic voting, which is a similar application to auctions, the homorphism of the encryption scheme may allow an observer to "gather" the encrypted results, and then only verify the "sum" of encrypted votes. However, in an auction application, this is not the case. So there is a need for the Auctioneers (they are distributed, for bid-secrecy) to publish a shuffle of the decrypted bids, and then prove correctness of the decryption in zero-knowledge. Although I have read a few papers about mix-nets (in the e-voting context), I had not realized that the mix idea answered my question (although I should have :). Thanx for all folks who answered my question !! - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]