# Re-encrypting a message and proving that the message has not changed

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$$?

• Do you specifically need a new key-pair? I think this is doable using El Gamal with a ZKP, but I'm pretty sure you'd need to use the same key pair. Before attempting to come up with an answer, I'd just like to make sure I know what I'm dealing with. Also, what do you need to use this for. Is this homework, or....? – ymbirtt Nov 19 '18 at 13:57
• Is the encryptor cooperating? That is, is he required to cooperate in generating ciphertexts that can be proven to share the same plaintext (which would get around Viou's objection; a random third party wouldn't be able to) – poncho Nov 19 '18 at 14:33
• Are the key pairs required to be fully independent? If it were acceptable to have a set of key pairs that would allow anyone given both halves of one pair to find the private halves of all keys in the set when given the public key, I think RSA could work. If one uses one pair of primes to produce multiple key pairs with different public keys, then the result of encrypting a message using one public key and then another would be independent of the order in which the keys were used, but I'm not sure how useful that would be. – supercat Nov 19 '18 at 17:50

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

• El-Gamal has many tricks and one more. – kelalaka Nov 19 '18 at 19:44

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