# How can a recipient recognize which encrypted messages are intended for them?

Let's say there's a decentralized email service where parties' public keys are known. A sender sends a message to a recipient by encrypting via RSA with the recipient's public key and posting the ciphertext publicly somewhere where everybody can see, e.g. a public blockchain.

Senders don't want others to know which addressees they're communicating with, so they only publish the ciphertext. Then everyone needs to scan the blockchain for new events and try to decrypt each message with their private key (in the RSA-AES hybrid scheme, they will try to decrypt a one-time AES key the message is encrypted with). If they succeed (and let's say the prefix of the recovered message is their public key per protocol), it means the message is intended for them.

The above scheme requires every participant apply RSA decryption to every message, and the number of messages per time unit are expected to increase. Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?

One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages. This way, each revealed bit splits the number of potential recipients in half (starting from everybody when 0 bits are revealed and halved with each bit), while still not allowing outside observers to determine the exact recipient, but it does allow everyone else to save computing cycles skipping exponentially larger amount of messages.

However, I'm interested to know whether there are even better approaches.

• Not really an answer, but Signal's sealed sender (signal.org/blog/sealed-sender) might be interesting for your problem. It prevents others from knowing who communicates with whom, but it does so by hiding the sender more than the receiver – Andrea Apr 11 at 21:52
• Please consider the following: How are new participants announced to existing ones? Must all the participants present their PK on the block-chain, or can they establish comm's on a more secure channel? Do participants' PKs remain constant, or change over time - ie. what is your response to a participant's key compromise? Are messages uni-directional (ie. from an anonymous sender), or are parties authenticated in both directions? – brynk Apr 13 at 7:33
• @brynk New participants announce by registering an unoccupied handle ("email address") on the blockchain, thereby attaching their PK to it. It is possible that they can change the attached PK if they have control over their private key. Various methods might be used when the key is compromised (social recovery, second vaulted/airgapped private key with more authority etc). All clients will follow new PK for new messages. Messages are authenticated both ways, not anonymous, but it's fine if the signature proving the sender identity is inside the encrypted blob. – Serge Uvarov Apr 13 at 10:53

Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?

It doesn't appear that the problem of recognizing the message (without leaking who the message is for) can be significantly faster than public key decryption. Let me be more precise; suppose we had a way such that:

• Alice can publish some public information
• Bob can use this information to generate a 'tag'
• Alice can check to see if this tag was generated with her public information
• No one without Alice's private information can do so (if not, anyone can check if the tag was flagged to be of interest to Alice).

If we have a primitive that can do that, then Alice can use that primitive as a public key encryption method; the method isn't very efficient (in the simplest case, Bob would generate a series of 'tags', where each tag encodes a bit - one bits are tagged with Alice's information, and zero bits are not); however it is sufficient to indicate that the problem isn't inherently easier than the general public key encryption problem.

So, what can we do? Well, the best I can suggest is use a public key encryption method that's more efficient than RSA; here are two ideas:

• ECIES; here, the decryption operation is a point multiplication (and a handful of symmetric operations); significantly cheaper than RSA

• NTRU; this is a NIST postquantum level 3 candidate with (to use a technical term) honkin' fast decryption; for example, the ntruhps2048677 parameter set is listed as using only 59,729 Haswell cycles.

Of course, you could also separately RSA encrypt the message along with the tag; however, given that by validating the tag, you've essentially done most of the work, you might want to just use ECIES or NTRU.

Also, one comment on your idea:

One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages

Does that mean that, in the ciphertext, you expose k bits of the public key, where k gradually increases as the number of messages increases? Well, one problem with that is, while an eavesdropper can't generally be certain who the message is for, he can be pretty sure who it is not for - that many be just as bad...

How this general kind of thing is handled today is with hybrid encryption. A symmetric key is generated and the message is encrypted with that. Then the symmetric key is key wrapped (encrypted) using the public key of each intended recipient. (Keep in mind that RSA can only encrypt small amounts of data.)

This only encrypts the data once. You can make it so that the recipients don't know who else can decrypt the data. It does leak how many recipients there are, but you can probably do something like pad with fake data to simulate other recipients that aren't real to mask that.

• Did you read the 2nd paragraph? – kelalaka Apr 11 at 18:15
• @Swashbuckler sorry, this does not answer my question at all. Your answer seems to be about encrypting the same message to many recipients, while my question is about encrypting different messages to different recipients, and letting them recognize which one was intended for them. – Serge Uvarov Apr 11 at 20:22