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]
