Argthtjtr

Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?

More specifically: if I have a message $m$, and I encrypt it with an asymmetric key scheme $E_1: c_1 = E_1(m)$ and then re-encrypt it with a new key pair $E_2: c_2 = E_2(m),$

is there a way for an observer (possibly using a ZKP or homomorphic encryption) who only has access to $c_1, c_2$ and the public keys of $E_1$ and $E_2$ to prove that $m$ is the same plain text used to generate $C_1$ and $C_2$?

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'$.

I think this is not compatible with semantic security (IND-CPA). If such a proof exists, an adversary that chooses $(m_0,m_1)$ and receives $c_b=E_1(m_b)$ may compute $E_2(m_0)$ and try to prove that $m_b=m_0$. If the proof is correct, then he guesses that $b=0$, else $b=1$. But may be there exist weaker security models that allow to test the equality of two plaintexts.
Your problem seems similar to plaintext checkable encryptions.

One weak solution can be based on Bongenaar' Multi-key FHE where;

In the multi-key FHE setting, we have $N$ participants with their own keypair $(sk_i, pk_i)$ and message $ m_i$, who want to perform computations on all data without revealing any private information to each other. After the computation decryption should only be possible when all the secret keys that were used to encrypt the messages
are involved.

Now we can use this scheme as follows;

• Encrypt the message $m$ with two different key, $pk_1,pk_2$ to get $c_1$, $c_2$
  


• The observer encrypts the message $m_0 = 0$ the zero message, $c_0$.


• Evaluate $c_1 - c_2 + c_0$ homomorphically using the scheme of Bongenaar's,


• decrypt the result.

The results;

• If the result is not zero, then they are not the same.


• Since we use semantic scheme, no one but the private key owner can decrypt $c_1$ and $c_2$ to reveal the $m_1$ and $m_2$
  


• 
  The observer must not be allowed to evaluate any other function, otherwise $c_1+c_2-c_0$ will reveal the $2m$. To mitigate, one can first evaluate $c_1-c_2$.