How can I prove I'm the recipient of an encrypted message without revealing my identity and the message?

Question

Alice wants to leave a message for Bob. So she encrypt a signed message with Bob's public key.

Then leaves it at a dead drop service.

Then later Bob arrives and checks the messages and attempts to trial decrypt all of them to see if there are any addressed to him.

When Bob finds Alice's message, he manages to decrypt and read it.

However in order to avoid the vandalization of the dead drop, he can only remove the message from the dead drop if he can prove he is indeed the recipient.

Is there a way to do that without revealing the message and his identity?

Answer 1

One possible approach to this may use a commitment scheme.

That when Alice deposits the message $m$, she signs $m$ resulting in the signature $\sigma$, then she picks a (eg 256-bit) random string $r$ and encrypts $(r,m,\sigma)$ into the ciphertext $c$. Now she creates a commitment $\rho$ (eg a SHA-256 hash of $r$) for $r$ and publishes $(\rho,c)$ at the dead drop.

When Bob retrieves the message, he decrypts $c$, yielding $(r,m,\sigma$) and then opens the commitment (e.g. presenting $r$ such that $H(r)=\rho$) to the operator, who can now know that Bob was indeed able to decrypt the ciphertext. But because $r$ is a random string it doesn't leak anything about $m$.

Of course, while this solution works, it assumes that Alice is actually "honest" and doesn't encrypt something without also leaving the solution to the commitment behind (and thus taking up space that can never be reclaimed). Of course it depends on your concrete situation whether this suffices or whether you want a more sophisticated scheme (of which there some I think).