anonymous comment on Zero-Knowledge proofs for valid decryption ! !

Andy Neff aneff at votehere.net
Tue Jul 10 17:47:48 EDT 2001


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



-----Original Message-----
From: lcs Mixmaster Remailer [mailto:mix at anon.lcs.mit.edu]
Sent: Monday, July 09, 2001 9:21 PM
To: cryptography at wasabisystems.com
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
majordomo at wasabisystems.com



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




More information about the cryptography mailing list