Assume there is a global message board, that people use to send messages to other people. Of course no one else but the receiver should know the content of the message, so senders use asymmetric cryptography to encrypt the message for the receiver.

To determine if a message on the board was meant for me, I could try to decrypt all ciphers on the board and see which message makes sense. Maybe there is a phrase, that is commonly used by everyone, that is also separately encrypted and then I can decrypt all those fields and see if I recognise the phrase.
Of course I could also add the receivers public key in plain text to the message, but then everyone would know who the message is dedicated to (without knowing the content), which shouldn't be possible.

In the worst case I need to decrypt all messages on the board to find the one dedicated to me, which is not very efficient.

Is there a better way that allows me to add a "sign" for the receiver that only the receiver can recognise?

I'm sorry if this is a common and known problem, but after some research I didn't came up with the commonly used terms for the problem, if this problem has a name.

Edit: Pre-shared information between the receiver and the sender is not possible, because the receiver doesn't know, they will receive something.

  • 1
    $\begingroup$ Bitmessage essentially does this (with the global board being a P2P network and decryption confirmation being handled using MACs). I think the term you need to find more info on this is Private Information Retrieval. $\endgroup$
    – SEJPM
    Commented Dec 5, 2019 at 12:51
  • $\begingroup$ as far as I understood a Bitmessage client needs to download all messages in the pool and test if they can decrypt it $\endgroup$ Commented Dec 5, 2019 at 14:35
  • 1
    $\begingroup$ Exactly, it does the "bad" solution you suggested. $\endgroup$
    – SEJPM
    Commented Dec 5, 2019 at 14:36
  • 1
    $\begingroup$ A similar question (without any good answers) is crypto.stackexchange.com/questions/30148/… $\endgroup$
    – poncho
    Commented Dec 5, 2019 at 20:03


Your Answer

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

Browse other questions tagged or ask your own question.