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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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