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]

- Zero-Knowledge proofs for valid decryption !! Emmanouil Magkos
- Re: Zero-Knowledge proofs for valid decryption... Helger Lipmaa
- FW: Zero-Knowledge proofs for valid decryption... lcs Mixmaster Remailer
- FW: Zero-Knowledge proofs for valid decryption... Andy Neff
- Re: FW: Zero-Knowledge proofs for valid decryp... lcs Mixmaster Remailer
- Re: FW: Zero-Knowledge proofs for valid de... Emmanouil Magkos

- Re: Zero-Knowledge proofs for valid decryption... lcs Mixmaster Remailer