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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

I think you can reduce the burden of asymmetric operations by making the protocol have 2 classes of messages:

• Invitation messages: they are encrypted with the recipients' public keys and contain secret states $S_T$ and $S_K$. You don't need these messages if key sharing out of the band is possible. Everyone needs to try to decrypt these to check if they are the ones who are invited or they can simply discard them if they are not willing to accept invitations.

• Communication messages: they are symmetric encrypted messages as described below. They can quickly be discarded if it's not meant for the recipient.

Let $R$ be an cryptographically secure random number generator, such that $(t, s_2) = R(s)$, where $t$ is the generated random sequence, $s_2$ is the new state, $s$ is the old state. Let $E$ be a symmetric encryption algorithm such that $c = E(k,m)$, where $c$ is the ciphertext, $k$ is the key, $m$ is the message. Let $E^{-1}$ be the inverse of the $E$ such that $m = E^{-1}(k, c)$. Let $H$ be a cryptographic hash function such that $h = H(m)$, where $m$ is the message $h$ is the hash. Let $D$ be a key derivation function such that $K = D(k)$, where $k$ is a random input $K$ is a symmetric key.

Let Alice and Bob agree upon two randomly chosen shared secrets $S_T$ (tag RNG state) and $S_K$ (key RNG state) as well as note the next block index $i$ in the block chain. This should be done in person or an authenticated secure channel.

Alice sends a message $m$ to Bob like this:

1. Make sure she is up to date with the block chain (see Bob's section)
2. Generate a sequence of bytes $T$ so $(T, S_{T2}) = R(S_T)$.
3. Generate a symmetric key $K$: $(k, S_{K2}) = R(S_K)$, then $K = D(k)$.
4. Calculate the hash $h = H(m)$
5. Encrypt the message using $E$ to get ciphertext $c = E(K,m || h)$
6. Publish $T || c$.

When Bob checks for new messages he would:

1. Generate a sequence of bytes $T$ so $(T, S_{T2}) = R(S_T)$.
2. Get the next block at index $i$; stop if no new blocks.
3. Increase $i$.
4. If the block we got doesn't start with $T$ (simple string comparison), go to 2.
5. If it starts with $T$, then treat it as $T || c$ and proceed.
6. Generate a symmetric key $K$: $(k, S_{K2}) = R(S_K)$, then $K = D(k)$.
7. Then decrypt: $m || h= E^{-1}(K, c)$
8. Check if $h = H(m)$. Discard message if it doesn't match. Consider it received if it matches.
9. Update states $S_K := S_{K2}$, $S_T := S_{T2}$.
10. Go back to step 1.

Alice would also check the blockchain the same way, and would find her own message just like Bob would. Finding her own message would confirm successful submission. The protocol should have a nick name field or a proper signature needs to replace $h$ to determine who said what.

If an adversary tampered with $T$, then none of them would recognize the message and possibly resubmit it with the same $T$. If an adversary tampered with $c$, both of them would reject it and still advance the RNGs for the next try so $T$ won't be reused.

$T$ needs to be long enough to avoid collisions by random chance.

And all users need to see the same block chain otherwise RNGs would go out of sync.

$S_T$ and $S_K$ essentially define a chat room. Whoever has them can read and write all messages. So people can be invited by sharing the state to them. But people can only be kicked by having the remaining parties agree upon a new shared secret.