Assume we have the situation that Alice is receiving somewhere in the magnitude of 1_000_000 encrypted messages, whereby a small number (n<100 for 99% of cases) of these messages are meant for her. An outside observer should not be able to tell which of these messages are meant for Alice, so we can't just send the ciphertext along with some identifier for Alice to look for.
The way I'm currently doing this is by having the senders of messages for Alice take Alice's public key and perform an ECDH key exchange with her key and an ephemeral key to find a shared secret and then use this to encrypt the message to Alice using an authenticated encryption scheme. That way Alice knows if the decryption fails that the message wasn't meant for her. Problem with this is the first step on Alice's end, doing ~1_000_000 key exchanges (or even 10_000) to check each message is incredibly slow.
I've been racking my brain trying to think of some other clever way to make the messages detectable for only Alice without having to do a key exchange everytime or make it faster some other way, but can't seem to think of one, so I'd be very grateful for any suggestions :)