Possible to encrypt message without knowing recipient public key?

Question

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?

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!