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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    Apr 3 '21 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: enter image description here

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$

  • $\begingroup$ Thank you so much for the detailed answer! $\endgroup$
    – krkhan
    Jun 1 '21 at 16:45

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.