Zero-Knowledge proofs for valid decryption !!

lcs Mixmaster Remailer mix at anon.lcs.mit.edu
Mon Jul 9 17:00:15 EDT 2001


Emmanouil Magkos writes:
> 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})

The problem can be reduced to the following: Given ElGamal ciphertext
E(m), reveal m and prove that it is the plaintext, without revealing
the private key s.  This is a subset of the problem above for the case
of 1 element, so if the problem above is solvable, this is.  And we can
show that if we can solve this, we can solve the above:

Choose another random value t and compute ( g^t * g^r, h^t * h^r * m ),
for each of m_1, m_2, m_3.  Then publish these values in a random order
(independent of the random order of the displayed m plaintexts).

Now we do a cut and choose.  The challenger picks 0 or 1 at random.  If 0
we will show that these are re-encryptions of the original ciphertexts.
If 1 we will show that these are encryptions of the claimed plaintexts.

For the 0 case, reveal t and the random order.  The challenger can verify
that the values are computed as claimed (multiplying the first terms by
g^t and the second by h^t and see if they match the claimed values).

For the 1 case, reveal the mapping between these new values and the
claimed plaintexts.  Now we have a set of ElGamal encryptions of the
plaintexts, using t+r as the exponent.  The prover doesn't know t+r,
but he can decrypt them using his private key s just as for any other
ElGamal encryption.  All he has to do is to solve the problem above of
showing that a plaintext corresponds to an ElGamal ciphertext, without
revealing his private key.

Repeat the cut and choose k times for a security level of 2^k.  This can
also be done non-interactively by standard procedures originating from
the Schnorr signature.  Thus the two problems are shown to be equivalent.

Now, as for proving validity of ElGamal decryption.  Let E(M) = (A, B)
where A = g^r and B = h^r * m.  We want to show that there is a value s
(which we won't reveal but where we have published h = g^s) such that
m = B / A^s.

Rearrange this to A^s = B / m.  In effect we want to show that the
discrete log of B/m to the base A equals the discrete log of h to the
base g.  This is a well known problem.  We do the Schnorr proof of
knowledge of a discrete log simultaneously on g^s = h and A^s = B/m,
as follows:

Choose a random value u and publish C = g^u and D = A^u.  Challenger
gives a random x.  Prover responds with y = (u + sx).  Verifier checks
the following:

g^y = g^u * (g^s)^x = C * h^x
A^y = A^u * (A^s)^x = D * (B/m)^x

If both equalities hold for the left and right terms, the proof is
established.

Again, the Schnorr heuristic can be used to make these proofs
non-interactive.

Q.E.D.



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




More information about the cryptography mailing list