Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair?

I vaguely recall reading about a scheme that accomplished this but am not able to figure out which one it was. For the sake of brevity I'm gonna omit any nonces.

Let's say we have an asymmetric keypair: (Kpub, Kpriv)

An observer is provided: C1 = E(Kpub, P1)

P1 is known. It can verified that by performing E(Kpub, P1) the result is indeed C1.

The observer is then provided: C2 = E(Kpub, P2)

P2 is not known to the observer, but they are provided a proof that they can use to verify that C1 and C2 are indeed ciphertexts that can be decrypted by the same private key (or in other words; were obtained by encrypting using the same public key).

I think ElGamal and NIZK were part of the proof but I'm not sure. Any ideas?

• Note that in general for public key encryption an adversary can in fact not tell whether a given ciphertext originated from a given randomness, unless they know the private key or can guess the randomness used during encryption. – SEJPM Apr 3 at 10:47

Chaum-Pedersen protocol tweaked with Sigma AND composition should do.

The high level intuition: using Chaum-Pedersen protocol for DH-triple, one can prove knowledge of secret witness $$\alpha$$ in the following relation in (honest verifier) zero-knowledge:

$$\mathcal{R}:=\left\{((x, y, z), \alpha)\in\mathbb{G}^3\times\mathbb{Z}_q: \quad y=g^\alpha \land z=x^\alpha\right\}$$

where $$(x,y,z)$$ is the statement ("claiming that they are a DH-triple")

Recall the following ElGamal encryption scheme:

Now let $$y$$ be your public key and $$\alpha$$ your secret exponent (secret key), let $$x$$ be the first part of the ElGamal ciphertext above (namely $$v$$ in the screenshot), and naturally $$z = y^\alpha = g^{\alpha\cdot\beta}$$ is the shared secret and let it be the $$w$$ in the ElGamal encryption process.

With Chaum-Pedersen Sigmal protocol above, we can prove knowledge of a secret key that produce a ciphertext for a certain message.

Finally composing two Sigmal protocols, one for each (message, ciphertext) tuple, using AND-proof construction, the verifier could easily verify that the two ciphertexts are encrypted under the same key as the two statements shared the same $$y$$. $$\blacksquare$$

Not using El Gamal.

For any given El Gamal public private key pair, every pair of group elements $$(a,b)$$ represents a legitimate El Gamal encryption of some message.

In other words, for any given $$C_2$$ there exists some $$P'_2$$ that encrypts to $$C_2$$ under the same public/private pair used for $$P_1$$ and $$C_1$$. If a different key pair were used, we would have no way of knowing unless there we have some knowledge about $$P_2$$.