# Proof of public-key encryption

Let us assume three entities: $$A, B,$$ and $$C$$, and let $$[p_C, P_c]$$ the private/public key pair of $$C$$. Assume that $$A$$ encrypts a message $$m$$ using the public key of $$C$$, $$P_C$$, and sends this encrypted message $$c$$ to $$B$$.

My question is: can $$B$$ somehow discriminate that the encrypted message $$c$$ is the result of the public-key encryption of a value with the public key $$P_c$$? (public keys are public, so known to everybody).

• @JohnDeters actually an unclear question since the public key cryptosystem is not defined! Dec 10, 2021 at 18:49
• To solve my problem, I am actually looking at the properties of the encrypted message itself, without considering any metadata. I left the public key cryptosystem intentionally general, just because I am looking for a public key cryptosystem which allows you to have this property (sort of proof that a specific public key has been used). Dec 10, 2021 at 20:49
• That was unclear from your question. Why do you need this? Dec 10, 2021 at 22:59

If you encrypt the message using the public key of C entity (P_c) and send it on B through entity A, the entity B could not decrypt the m to understand it content because the encrypted key belongs to another entity and not in the entity of B. So when B receive the encrypted message, will try to decrypt it using private key of B but because the m is encrypted with public key of C, B will not manage to decrypt it and will drop it.

• What happens if TextBook RSA is used? The PKC is not defined, so unclear question. Dec 10, 2021 at 18:51

can B somehow discriminate that the encrypted message m is the result of the public-key encryption of a value with the public key P_c?

It depends on the public key algorithm. With RSA, for example, the encrypted session key value (which is public) is always less than the value of the RSA encryption modulus (which is also public) used to encrypt it.

If it is the case that key C's public RSA modulus is greater than keys A and B's, then a session key encrypted by key C could also be greater than A and B's public modulus. In such a case it would be known neither key A nor key B could have produced it.

• Have you ever heard RSA-KEM? Dec 10, 2021 at 20:17
• @kelalaka I don't see how RSA-KEM and (e.g.) RSA-OAEP are different for this answer. Either way, the possible range of RSA ciphertexts is different for different keys, and that can be a practical distinguisher if you have enough ciphertexts relative to the number of potential keys. Dec 11, 2021 at 9:23

No, it's not possible to B to know anything about the message itself, unless it contains metadata. The message itself is just a opaque block of binary data. It's possible to infer the algorithm used for encrypting, but not much more than that.

If the message have metadata describing it, things change. But they change only because there's a field somewhere saying "Encrypted by A using C public key", not because any intrinsic property of the message.