FW: Zero-Knowledge proofs for valid decryption !!
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]
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]
