1
$\begingroup$

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 :)

Improve this question
$\endgroup$
9
  • $\begingroup$ Thanks for the suggestion, but as I said in my question an outside observer should not be able to tell what messages are for Alice. $\endgroup$
    – Guiomar Raissa
    Sep 21 at 14:58
  • $\begingroup$ Let me clear; does outside observer had the key to decrypted? first block of every message $Enc(K, FORALICE \| the\_message)$, I did not mean the ciphertext, the first block of every plaintext is the intention. $\endgroup$
    – kelalaka
    Sep 21 at 15:00
  • $\begingroup$ What would K be in this case? If it's the shared secret derived via ECDH, this unfortunately doesn't solve my problem, as the bottleneck for me isn't the decryption of every message, but the initial ECDH key exchange to derive the shared secret. Determining what messages are for Alice already works via authenticated encryption like stated in my question, the problem is just the initial key exchanges are too slow. $\endgroup$
    – Guiomar Raissa
    Sep 21 at 15:01
  • $\begingroup$ have you ever considered that the DHKE is two pass? It is single pass. Send all this; $$g^y\|Enc(k, FORALICE) \|tag_1 \|Enc(k,\text{the message})\|tag_2.$$ Alice tries to open and see correct or incorrect tag. For false positive, still keep some header on the message. $\endgroup$
    – kelalaka
    Sep 21 at 15:08
  • $\begingroup$ I'm using x25519 as my curve with which I perform it, so that should be multiplicative if I'm not mistaken. Your suggestion is cool, but still requires a scalar multiplication from Alice using g^y and her private key, which is equivalent to ECDH, right? $\endgroup$
    – Guiomar Raissa
    Sep 21 at 15:14

2 Answers 2

Reset to default
1
$\begingroup$

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 :)

Let us assume that the requirement is that we give sender A some public information that allows him to tag the message for someone specific, but cannot determine if how sender B (with the same public information) has tagged sender B's messages.

With that assumption, then we can implement public key encryption with that method (and hence we are unljkely to come up with a scheme that is more efficient than existing public key encryption algorithms).

The method for doing public key encryption is straight-forwards; we take each bit of the plaintext, and if that bit is 1, we generate a message that is tagged to the receiver (using the receiver's public key); if that bit is 0, we generate a message that is tagged to someone else; we then bundled those messages together and send them. We can see that this is secure (because someone with only public information cannot determine who any of the messages are intended for), and that the intended recipient can decrypt the message (because we assumed that she could determine whether each message was intended for her or not).

This shows that, to do this more efficiently than public key encryption, we need to change the requirements; possibly by having a long term shared secret key between Alice and the sender. aiootp outlines one plausible way, by having Alice and the sender performing a key exchange between them beforehand to establish such a shared secret.

Improve this answer
$\endgroup$
0
$\begingroup$

some other clever way to make the messages detectable for only Alice without having to do a key exchange everytime

If the AEAD scheme accepts an IV, & the peers have previously made & remembered the secret state from their previous communication session, then they could use that shared state & IV to derive then embed a pseudo-random message ID as the IV. Something like this:

$$K_{commit}, \space\text{IV} = \mathrm{KDF}(K_{shared}, \space\text{msg#}, \space\text{msg_type}, \space\text{sender_id}, \space\text{receiver_id})$$

Alice now stores the IV, and can efficiently scan the incoming messages for the IVs which match any of her stored IVs. The IVs here function as the next message IDs for her existing connections. If the IV matches, then Alice can derive the message key and attempt to decrypt the following type of ciphertext message.

$$K_{msg} = \mathrm{KDF}(K_{commit}, \space K^{eph\text -pub}_\text{Bob}, \space K^{pub}_\text{Alice}, \space\text{ECDH}(K^{eph\text-pub}_\text{Bob}, K^{priv}_\text{Alice}), \space IV)$$

$$\text{ciphertext}_{\mathrm{Bob}\to\mathrm{Alice}} = K^{eph\text -pub}_\text{Bob} \parallel \mathrm{AEAD}(K_{msg}, \space IV, \space A, \space\text{plaintext})$$

This method also works if the AEAD scheme accepts a $n_{once}$ since the message key also changes with every message.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ If Alice shares a secret value with the sender, it's easy. What's trickier is how to give the sender some public information that allows him to tag messages as 'for Alice', but without being able to detect if other senders have so tagged such messages. If you have such a scheme, you can use it to perform public key encryption, hence it cannot be easier... $\endgroup$
    – poncho
    Sep 21 at 15:57
  • $\begingroup$ @poncho mmm, that's true. if we know there's an easy solution if the problem looks a certain way, then if we can, we should probably figure out how to transform the problem into that easy thing instead of trying to solve the hard thing up front. $\endgroup$
    – aiootp
    Sep 21 at 16:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.