Is it possible to derive the recipient's public key from libsodium's crypto_box?

Question

Libsodium has "crypto_box_seal" which according to the documentation is used to "anonymously send messages to a recipient given its public key.", which hides the sender.

But Is it possible for Eve to know/confirm the exact public key of the recipient from a message made from crypto_box/crypto_box_seal, assuming that Eve already has a list of public keys that it could be?

Answer 1

You are given $E_{H([ab]P)}(n, m)$ and $[b]P$, where

• $E$ is an authenticated encryption function,
• $H$ is a hash function,
• $a$ is the recipient's secret key and $[a]P$ is the recipient's public key,
• $b$ is the sender's secret key and $[b]P$ is the sender's public key,
• $P$ is the standard base point on the standard curve,
• $n$ is a nonce, and
• $m$ is a message.

Your task, as stated, is to find which of $[a_1]P, [a_2]P, \ldots, [a_k]P$ is $[a]P$. Let's assume you already know $n$ and $m$; if you don't—if your knowledge about them has total min-entropy $e$ bits—then you'll probably have to iterate this process $2^e$ times. Let's simplify it a little bit and say you only want to tell whether $[a]P = [a_1]P$ or not; you can repeat it $k$ times to find which key among the choices, if any.

Suppose you have a random algorithm $A(Q, R, c)$ that returns 1 with high probability for $A([a]P, [b]P, E_{H([ab]P)}(n, m))$ and returns 0 with high probability for any other inputs. Then I can define an algorithm $A'(Q, R, S) = A(Q, R, E_{H(S)}(n, m))$ that serves as a distinguisher for the decisional Diffie–Hellman problem in the group generated by $P$, because it returns 1 for $A'([a]P, [b]P, [ab]P)$ with high probability and returns 0 for any other inputs with high probability.

So the answer is: No, Eve cannot even confirm the recipient just by examining the ciphertext. This property is sometimes called key privacy or anonymity. (The formulation in the paper is slightly different, but I think it is equivalent; if not, adapting the proof to the formulation in the paper is left as an exercise for the reader, since most DH-based schemes naturally exhibit key privacy, unlike RSA-based schemes.)