Assume Bob is sender and Alice is future recipient.

In ideal situation Bob know Alice public key, and encrypt message with it.

But what if Bob don't know Alice public key (he only will know Alice public key when agreement met), I saw two solutions:

  1. Bob encrypt message with Alice pub key after agreement met and pub key revealed
  2. We have 3rd party, let's say Kate. Bob encrypt message and give symmetric key to Kate. After agreement met, Kate re-encrypt it with Alice pub key.

However, in first scenario we rely on Bob (he could not encrypt/send message after agreement met), and on second scenario we rely on 3rd party Kate (she could know original message (by re-encrypt with own pub key), + she could not send message after agreement met too)

Is it possible to do without rely on Bob or Kate but also take into consideration that Alice pub key is unknown at time Bob encrypting message.

Or if we use Kate scenario and rely on 3rd party, is it possible that she couldn't know original message?

  • 2
    $\begingroup$ Third possible solution: use Identity Based Encryption, where the public key is something already known to Bob (for example, Alice's name). $\endgroup$
    – poncho
    Dec 4, 2023 at 1:26
  • $\begingroup$ This is for ideal case. In my case Bob and Alice don't know each other (no information at all), until agreement met. So I'm searching ways how to encrypt message without knowing recipient, and don't rely on sender or 3rd party. (But 3rd party is ok, if he couldn't know original decrypted message) $\endgroup$
    – byXrom
    Dec 4, 2023 at 8:27
  • 1
    $\begingroup$ I don't get the problem. Why does Bob send a message to an unknown identity? May be you need a hash commitment about the encryption/message so that later when you want to the message to Alice, you can send the key, message, and commitment so that Ailce can be sure that the message was sent way earlier than now, even their birthday. $\endgroup$
    – kelalaka
    Dec 4, 2023 at 9:45
  • $\begingroup$ Bob sending message to unknown identity, because he don't know who will met agreement. It can be Alice, but it can be someone else. So whoever met the agreement should be able to decrypt original message. Yes we can use hash. It will add trust for Alice or other person who can verify that message is original. But we still rely on Bob. He can walk away and don't send anything after agreement is met $\endgroup$
    – byXrom
    Dec 4, 2023 at 10:49
  • $\begingroup$ Since you mention "until aggrement is met", does it mean some interaction is accepted in your use case? In that case, authenticate key establishment with post-specified peers might be a solution. Such an AKE allows two parties to establish a secure channel even if they didn't know they who they wanted to talk to. The AKE guarantees that the identity claim of your peer is indeed true and that messages can be sent securely once a session key is established. $\endgroup$ Dec 4, 2023 at 12:13

1 Answer 1


What about:

  1. Bob publishes a public key for some secure signature system. Alice trusts it, or will get a way to trust it.
  2. Bob draws a random secret 256-bit key $k$.
  3. Bob symmetrically encrypts the message $M$ into ciphertext $C$ using key $k$ and some (optionally: AEAD) algorithm, e.g. AES-256 or AES-256-CTR.
  4. Bob computes $h=\operatorname{SHA3-512}(k)$.
  5. Bob publishes $C$, $h$, an a text $T$ promising he will proceed by the protocol when he gets a trusted RSA public key of at least 2048-bit from Alice by some stated procedure. With this he publishes his signature of $C\mathbin\|h\mathbin\|T$.
  6. Alice checks Bob's signature, and aborts if that fails.
  7. Alice publishes her public key $(n,e)$ by some procedure Bob stated he will trust.
  8. Bob gets the public RSA key $(n,e)$ of Alice and checks that it meets his stated expectations.
  9. Bob computes a random or pseudorandom bitstring $u$ of $\bigl\lfloor\log_2n\bigr\rfloor-256$ bits (that can be by hashing $k\mathbin\|n\mathbin\|e$ with $\operatorname{SHAKE256}$).
  10. Bob computes $v=(u\mathbin\|k)^e\bmod n$.
  11. Bob publishes $v$, with his signature of $v\mathbin\|h$.
  12. Alice checks Bob's signature, and aborts if that fails.
  13. Alice computes $(v^d\bmod n)\bmod2^{256}$ which is $k$, checks $\operatorname{SHA3-512}(k)=h$, and deciphers $C$ into $M$.
  14. If Bob cheated by sending an incorrect $v$ w.r.t. $k$ and/or $h$, Alice can prove that by computing and revealing $w=v^d\bmod n$. Anyone can check $w^e\bmod n=v$ but $\operatorname{SHA3-512}(w\bmod2^{256})\ne h$, proving the dishonesty of Bob.
  15. If Bob cheated by sending an incorrect $C$ w.r.t. $k$ and $h$ (that is $C$ deciphering to nonsense or not deciphering at all for AEAD), Alice can prove that by revealing $k$, allowing anyone to check $\operatorname{SHA3-512}(k)=h$ and attempt the decryption.

One flaw with this protocol is that when Alice publishes $w$ given $v$ at step 14, that can compromise the confidentiality of one (but no more) earlier message sent to Alice per this protocol (and Alice has no way to prevent that even if she keeps an history of previous exchanges, due to potential RSA blinding). Therefore, if Alice's public key is used more than once, that can only be for messages which confidentiality quickly becomes moot (like: code for entry of the day). I welcome an improvement without such flaw!

  • $\begingroup$ In step 8 and later - we still rely on Bob. What if Bob just run away and do not additional commitment? Is it possible to have 3rd party to control it, but not be able to decrypt original message? $\endgroup$
    – byXrom
    Dec 4, 2023 at 11:03
  • $\begingroup$ @byXrom If Bob can get away with not pursuing the protocol and we do not want to trust a third party with the message, then I see no way to avoid that Bob encrypts worthless rubbish. $\endgroup$
    – fgrieu
    Dec 4, 2023 at 17:51

Your Answer

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

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