FW: Zero-Knowledge proofs for valid decryption !!

[Andy Neff]

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.
aneff at votehere.net




-----Original Message-----
From: Helger Lipmaa [mailto:helger at tml.hut.fi]
Sent: Monday, July 09, 2001 6:50 AM
To: Emmanouil Magkos
Cc: cryptography at wasabisystems.com
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
majordomo at wasabisystems.com



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