3
$\begingroup$

I know this seems a bit contrived, but I’m a layperson to cryptographic systems and have been trying to think if it’s possible to devise a scheme where it’s possible for a sender to prove, in a public key cryptosystem, that a given ciphertext was encrypted with a given public key, without significantly weakening the security properties of the ciphertext. It seems like there’s no obvious way to do this using typical primitives you’d find in a public key cryptosystem. I have been wondering if it is perhaps possible to devise such a scheme with the help of homomorphic encryption, but I simply can’t wrap my head around how you might go about this.

Is this an impossible, or perhaps at least impractical, problem? Is there perhaps another way to think about this that would be practical?

$\endgroup$
2
  • $\begingroup$ Maybe it could be possible to achieve your goals through the use of commitments, but it would depend on your use case. If you have a particular use case in mind, please elaborate on it. $\endgroup$
    – knaccc
    Jun 25, 2022 at 7:09
  • $\begingroup$ To be more precise, given a ciphertext $c$ and a public key $pk$, is such a proof supposed to prove the statement: there is a message $m$ and randomness $r$ such that $Enc(pk, m; r) = c$? $\endgroup$
    – Myath
    Nov 22, 2022 at 3:28

3 Answers 3

2
$\begingroup$

Yes, it is perfectly possible to prove that a ciphertext $C$ is of the form $\mathsf{Enc}_{\mathsf{pk}}(m;r)$, where $m$ is an arbitrary plaintext, $r$ an arbitrary random coin (both secret), and $\mathsf{pk}$ is a (known) public key, without revealing anything more beyond this fact.

Proving that something is true without revealing anything more beyond this fact is the realm of zero-knowledge proof, an active area of cryptography, I encourage you to look it up.

A few remarks, though:

  • Zero-knowledge proofs exists for all $\mathsf{NP}$ statements, meaning, all statements of interest. However, for generic, unstructured encryption scheme, they might be quite costly. They will typically be more efficient if the encryption scheme has some algebraic structure, which the proof can exploit.
  • One has to be careful about the statement itself: for some encryption schemes, it might not be meaningful!

Let me illustrate the second point with ElGamal encryption with public key $(g,h)$ over a group $\mathbb{G}$ of order $p$: a ciphertext $C = \mathsf{Enc}_{\mathsf{pk}}(m;r)$ where $m\in\mathbb{G}$ and $r\in\mathbb{Z}_p$ is constructed as $\mathsf{Enc}_{\mathsf{pk}}(m;r) = (g^r, h^r\cdot m)$. If it is not immediately clear to you, take some time to convince yourself that every ciphertext is a valid encryption under any public key for some $(m',r')$. Indeed, pick a different public key $\mathsf{pk}' = (g',h')$: there always exists some $(m',r')$ such that $C = ((g')^{r'}, (h')^{r'}\cdot m')$. Here, $r'$ would be $r\cdot a$ where $a$ is such that $(g')^a = g$ (which exists as $g'$ is a generator) and $m'$ would be $(h')^{-r'}\cdot h^r\cdot m$.

Hence, for ElGamal, proving that a ciphertext is a valid encryption under a given public key is a vacuous proof -- it is true for all ciphertexts. Nevertheless, we can instead prove something stronger, which probably matches more closely what you had in mind: we can use a proof of knowledge.

In a standard zero-knowledge proof, the prover proves that a property holds (e.g. $C$ is a valid encryption under $\mathsf{pk}$). But in a zero-knowledge proof of knowledge (ZKPoK), the prover shows that they know some piece of information. Here, you could ask the prover to demonstrate that they know a pair $(m,r)$ such that $C = (g^r, h^r\cdot m)$. Of course, such a pair always exists -- but in general, finding this pair is infeasible (you'd need to solve a discrete log), unless this is truly the pair you used to create $C$ in the first place! So here, using a ZKPoK would guarantee that indeed, the prover used the right public key to create the ciphertext. But it really depends on your context application whether this will be exactly what you want.

For some other schemes, however, the statement "$C$ was encrypted under $\mathsf{pk}$" is not vacuous anymore, and here even a standard zero-knowledge proof would make sense, depending (always) on the concrete use case you have in mind.

Just to finish: in the concrete case of ElGamal, proving knowledge of $(m,r)$ such that $C = (C_0,C_1) = (g^r, h^r\cdot m)$ for some public $(g,h)$ is equivalent to simply proving knowledge of $r$ such that $C_0 = g^r$ (indeed, you can always define $m$ from this $r$ as $C_1/h^r$ -- that's precisely ElGamal decryption). You will find many discussion, on this site and on the web, of methods to do exactly this proof, by looking up Schnorr discrete logarithm proofs. I'll let you have a look: it's a very simple interactive way to prove, without leaking any further information, that you know the discrete logarithm of a value.

$\endgroup$
1
$\begingroup$

Let's try re-framing the problem.

If your goal is to not store unencrypted data, in a service that acts as a key-value store of end-to-end encrypted messages between clients, a potential solution could be to have the server simply wrap the incoming data a second time, using the same public key. Then, upon retrieval of the ciphertext, the recipient could simply decrypt the message multiple times.

This does not solve the original problem of providing proof that the original plaintext is encrypted, but I think it's still an interesting approach that could have some ostensible benefit. Because it is impossible to tell ciphertext from random noise, this may potentially limit the liability of clients attempting to store illicit materials in plaintext maliciously.

The more I think about it, I'm not convinced this question or any of its solutions are very useful, but so far, I think this re-framing has the most useful solution.

$\endgroup$
1
  • $\begingroup$ I think this answer does not address the question at all... $\endgroup$
    – tylo
    Jun 26, 2022 at 6:07
1
$\begingroup$

I create some plaintext and a public/private key pair, then encrypt the plaintext. You crack my plain text. You can now create a hash of my plain text and send it to me. I can check the hash and will know that you have my plaintext. So proving it to me is simple.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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