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?

  • $\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 at 7:09

1 Answer 1


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.

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

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.