This kind of detail, I feel, is best taken "off line" between the interested parties. I would contact the author directly, but can't for obvious reasons. No, I do NOT use cut and choose in any form. (Please see my original post for a one sentence description of the basic idea.) That is where one finds the big win -- there is only one arithmetic challenge/response. The soundness, or "security parameter", is roughly $k/p$ "automatically". Since, in even exceedingly large applications $k$ is maybe 20-30 bits, and $p$ is 512-1024 bits, in practice, you will never get there with cut and choose. (Confession: I am somewhat put off by, what I -- perhaps mistakenly -- read to be, the implication that my work is derivative.) The remarks on application of CGS94 are essentially correct, however you must take more care to be sure that you have a permutation, not a map -- i.e. no duplicates. As written, you do not do this. Regarding the last five paragraphs of comments: All this is discussed in the paper and in the literature cited therein in much greater detail. Please forgive me if I misread the intent, but in this case, pedantry is not necessary. andy [EMAIL PROTECTED] -----Original Message----- From: lcs Mixmaster Remailer [mailto:[EMAIL PROTECTED]] Sent: Monday, July 09, 2001 9:21 PM To: [EMAIL PROTECTED] Subject: 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] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
