Is there a way to prove equality of plaintext that was encrypted using different public keys?

Question

Imagine if Alice encrypts message to Bob (using public key $P_{bob}$) and then Bob encrypts the same message to Carol (using $P_{carol}$). Is there a way for Bob to prove that:

1. $P_{carol}$ was indeed used
2. Message is still the same that Alice passed to Bob.

Note1: Both ciphertexts and public keys are visible for everybody who needs to verify this proof. Note2: Public keys and messages are new for every encryption so deterministic encryption is ok, but public key cryptography has to be used

It looks similar to this topic, but there only one public key is used: Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts? (comments from D.W and tylo are very helpful)

1. Obvious thought that comes to mind is to use commutative encryption, so everybody will be able to check whether $E_{bob}(E_{carol}(M)) == E_{carol}(E_{bob}(M))$ having $E_{carol}(M)$ and $E_{bob}(M)$ and access to $P_{bob}$ and $P_{carol}$. But then only deterministic encryption would work ($E_{bob}$ is encryption using $P_{bob}$).

2. The other solution that comes to my mind is using ZKP for DH 4-tuple if homomorphic encryption is used (for example El-Gamal - non-interactive proof is described here). So there is a way to prove that ($g$, $h$, $g^r$, $h^r$) is DH 4-tuple (where $h$ is public key, $r$ - random number, $g$ - generator of the group). In our case ciphertexts correspondent to message $M$ are $c_1=(g^{r_1}, M*P_{bob}^{r_1})$ and $c_2=(g^{r_2}, M*P_{carol}^{r_2})$. If to consider that $r_1=r_2=r$ (i.e. Alice also told Bob $r_1$) we can divide $c_1$ to $c_2$ and receive $(\frac{P_{bob}}{P_{carol}})^r$. Since everybody knows $P_{bob}$ and $P_{carol}$, Bob is able to create ZKP that $(g, (\frac{P_{bob}}{P_{carol}})$, $g^r$, $(\frac{P_{bob}}{P_{carol}})^r)$ is DH 4-tuple. In this way he can proof both statements (I believe :) ) Non interactive proof can be made. Having $c_1$ and $c_2$ Bob does:

   • selects random $r_3$
   • calculates $u=g^{r_3}$ and $v=(\frac{P_{bob}}{P_{carol}})^{r_3 }$
   • Calculates hash $d = H(u || v) $
   • Calculates $z=d*r+r_3$
   • Publishes $(u, v, z)$

Everybody is able to verify the proof $(u, v, z)$ doing:

• Calculating $d = H(u || v)$
• checking that $g^z == (g^r)^d * u$
• $(\frac{P_{bob}}{P_{carol}})^z ==({\frac{c_1}{c_2}})^d * v $

Are there any other methods?

Answer 1

Here is an answer to your question using a zero knowledge proof in the case of Elgamal encryption. The biggest difference between this solution and your own is that Alice does not need to tell Bob the value of $r_1$ anymore. This makes the zero knowledge proof more complicated.

Setting the scene:

Let $\mathbf{G}$ be the group of prime order $p$ in which the Elgamal encryption is taking place. Let $(g_1,h_1)$ be Bob's public key, and $s_1$ be Bob's private key, so that $g_1 = h_1^{s_1}$. Let $(g_2,h_2)$ be Carol's public key.

Let $(c_1,d_1) = (mg_1^{r_1},h_1^{r_1})$ be the ciphertext that Bob receives from Alice. Bob doesn't know $r_1$, but he does know that the decrypted message is $m = c_1 d_1^{-s_1}$.

Let $(c_2,d_2) = (mg_2^{r_2},h_2^{r_2})$ be the ciphertext that Bob sends to Carol.

Bob will use a zero knowledge proof to prove the following without leaking any information about $s_1$ and $r_2$:

-$s_1$ is the secret key corresponding to $g_1,h_1$

-$d_2 = h_2^{r_2}$, meaning that $r_2$ is the randomness used for $(c_2,d_2)$

-$c_2 = c_1 d_1^{-s_1} g_2^{r_2}$, meaning that the message obtained by decrypting $(c_1,d_1)$ with $s_1$ is the same as that encrypted in $(c_2,d_2)$

The Zero Knowledge Proof

Proof Statement: $(c_1,d_1),(c_2,d_2),g_1,h_1,g_2,h_2$

Bob picks $b_1,b_2$ uniformly at random from $\mathbb{Z}_p$. Bob computes $G_1 = h_1^{b_1}$, $G_2 = h_2^{b_2}$, $G_3 = d_1^{b_1} g_2^{-b_2}$

Bob computes a hash $x = h(proof statement || G_1 || G_2 || G_3)$ (I think it is necessary to include the statement in your original example too, but need to check).

Bob computes $\bar{s}_1 = s_1 x + b_1$ and $\bar{r}_2 = r_2 x + b_2$.

Bob publishes $(G_1,G_2,G_3,\bar{s}_1,\bar{r}_2)$.

Verification:

To verify, first compute $x = h(proof statement || G_1 || G_2 || G_3)$.

Check that $h_1^{\bar{s}_1} = g_1^x G_1$ (shows $\bar{s}_1$ is a randomised version of Bob's public key)

Check that $h_2^{\bar{r}_2}=d_2^x G_2$ (shows $\bar{r}_2$ is the randomness used in $(c_2,d_2)$)

Check that $c_2^x c_1^{-x} d_1^{\bar{s}_1} g_2^{-\bar{r}_2} = G_3$ (shows that the messages in both ciphertexts are the same)

Security Proof Sketch:

I'll sketch a proof that the underlying interactive ZKP where the verifier picks random $x$ from $\mathbb{Z}_p$ is secure, and then rely on the well-known fact that replacing this with the hash to get the above gives a secure NIZK protocol will full zero knowledge.

(Completeness) It's easy to see that an honest prover will always convince the verifier by substituting the honestly computed values of $\bar{s}_1,\bar{r}_2,G_1,G_2,G_3,x$ into the verification equations.

(Special Soundness) For the same $G_1,G_2,G_3$, if the prover could produce acceptable proofs with $\bar{s}_1,\bar{r}_2$ and $\bar{s}'_1,\bar{r}'_2$, for two different values $x,x'$, then we could extract Bob's secret key (and hence the message), and the randomness used in the second ciphertext. From the first verification equation, we can compute $s_1,b_1$, the discrete logs of $g_1,G_1$ with respect to $h_1$, such that $\bar{s}_1 = s_1 x + b_1$ and similarly for $\bar{s}'_1$. From the second equation, we can compute $r_2,b_2$, the discrete logs of $d_2,G_2$ with respect to $h_2$, such that $\bar{r}_2 = r_2 x + b_2$, and similarly for $\bar{r}'_2$. Substituting into the third verification equation, we have $\left( c_2 c_1^{-1} d_1^{s_1} g_2^{-r_2} \right)^x d_1^{b_1} g_2^{-b_2} = G_3$. This is a polynomial (in group elements) which is satisfied for two different values $x$ and $x'$, so all coefficients must be equal to the group identity. Taking the coefficient of $x$, we have that $c_2 = c_1 d_1^{-s_1} g_2^{r_2}$. In other words, the decryption of the first ciphertext, when encrypted, gives the second ciphertext.

(Special Honest Verifier Zero Knowledge) Given $x$, the simulator can pick $\bar{s}_1,\bar{r}_2$ uniformly at random from $\mathbb{Z}_p$, and then compute $G_1,G_2,G_3$ using the verification equations.

Answer 2

One idea is to use normal hybrid encryption. Bob can reuse the symmetric ciphertext and encrypt the symmetric key (material) again using Carol's public key. With a proper choice of authentication in the symmetric part, Bob will be unable to find another key that correctly decrypts the ciphertext to some other message. For example, HMAC has this property, assuming the hash function is secure.

Anyone could compare the symmetrically encrypted parts of the ciphertext and if they are identical the message, if decryptable, is the same.

Note the limitation: there would be no way for others to prove that Bob has actually encrypted the correct key for Carol. Only Carol would be able to check that, so it could be that the message will not decrypt at all. Or will in fact decrypt correctly, but with someone else's key.

For others to be able to verify everything as well, you could use a commutative algorithm for the public key encryption part. The use of hybrid encryption avoids the need for the whole scheme to be deterministic since Alice can (and should) use random symmetric keys.

Answer 3

Are you simply wanting Alice to sign her message to Bob?

Carol could decrypt Bobs message, check the plaintext hash against Alices signature, and prove it came from Alice.