Score:0

Proof of public-key encryption

in flag

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

kelalaka avatar
in flag
@JohnDeters actually an unclear question since the public key cryptosystem is not defined!
Transagonistica avatar
in flag
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).
kelalaka avatar
in flag
That was unclear from your question. Why do you need this?
Score:1
in flag

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.

kelalaka avatar
in flag
Have you ever heard [RSA-KEM](https://crypto.stackexchange.com/a/76857/18298)?
Gilles 'SO- stop being evil' avatar
cn flag
@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.
Score:0
in flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.