If we assume that the reencryptor is cooperating, that is, he consciously generates the re-encrypted ciphertext to make this proof easy, then it is possible.
The solution I have involves a variation of El Gamal over a pairing friendly curve.
Background:
In El Gamal, to generate the encryption of message $M$ to the public key $aG$, you select a random $r$, and output the pair $rG, r(aG) + M$; the decryptor knows $a$, and so compute $a(rG) = r(aG)$, allowing him to recover $M$.
A pairing friendly curve is an elliptic curve that has an efficiently computable function $e(A, B)$ that has the following properties:
- $e(aG, bG) = e(G, G)^{ab}$ (for any integers $a, b$, the exponentiation is over some group, typically the muplticative group of some finite field
- $e(G,G) \ne 1$ (which implies that $e(G, aG) = 1$ iff $a \equiv 0 \pmod q$, where $q$ is the prime curve order)
[END OF BACKGROUND]
Now, one modification I make to standard ElGamal is to have a randomized invertable mapping between the actual message $m$ and the point $X$ we actually encrypt; that is, there is a function $H(m, r)$, which takes a message $m$, and a random value $r$, and outputs a point $X$; there is an inverse function that takes $X$ and recovers the original $m$. This is needed to prevent an attacker from using the function $e$ to test if a particular ciphertext corresponded to a particular plaintext.
Ok, the encryption of the message $m$ to the public key $A = aG$ is:
$$(rG, rA + H(m, r'))$$
where $r, r'$ are random values. The decryptor (who knows $a$) can recover $m$ in the obvious way.
Now, if the encryptor decides to send two ciphertexts to two different public keys that can be tested by a third party to be identical, he uses the same $r, r'$ values.
Then, when this third party receives the two ciphertexts:
$(X, Y)$ to public key $A$
$(W, Z)$ to public key $B$
He first checks if $X = W$ (which should be the case if the encryptor is cooperating; the first element of the ciphertext doesn't depend on the public key.
If that passes, he then checks if:
$$e( G, Y-Z ) = e( X, A-B) $$
Here's how that works:
$X = rG$, where $r$ is the random value the encryptor selected for both ciphertexts
$Y = rA + H(x, r')$ and $Z = rB + H(x', r")$, where $x, x'$ are the two plaintexts.
So, we have
$e(X, A-B) = e(rG, A-B) = e(G,A-B)^r$
$e(G, Y-Z) = e(G, rA + H(x, r') - rB - H(x', r")) = \\
e(G,A-B)^{r} \cdot e(G,H(x, r') - H(x', r"))$
These two will be the same iff $H(x, r') = H(x', r")$, that is, if $x = x'$.