### Re: Zero-Knowledge proofs for valid decryption !!

Some corrections and clarifications:

> 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).

Actually this should be a different t for each ciphertext, otherwise g^t
can be figured out and the order revealed.  Also, it should be different
t values for each iteration of the cut and choose.

Although the problem statement assumed you don't know the r exponent for
the ElGamal encryption, maybe in some cases it could be made available,
embedded in the plaintext (typically r can be much smaller than m so
there may be room for it).  Then, decrypting the message would reveal r.

This allows for a greatly simplified cut and choose for the case 1,
where the mapping between the intermediate values and the claimed ElGamal
decryptions must be done.  The prover just reveals t + r mod (p-1) for
each element (this leaks no information about r), and this allows an
easy verification that the intermediate values are ElGamal encryptions
of the claimed plaintexts.  There is no need for the discrete log proof.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

### Re: Zero-Knowledge proofs for valid decryption !!

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 [EMAIL PROTECTED]

### 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]