How to exchange a secret through untrusted server in two steps? I have a web application where I control the server, however, it should not have any knowledge of secrets that are exchanged between its users. This server holds RSA public keys of each registered user and can be trusted to deliver the correct public keys for each user when asked for them. A user's RSA public key is provided to the server whenever they register with the server. Users belong to "teams" and a user can only join a team by way of invitation from another already registered user that is a member of the team.

Alice is already registered and needs to invite Bob to her team and also deliver a team member secret to Bob. Bob is not registered yet, so Alice cannot ask the server for Bob's public key. Right now I have implemented this type of team member exchange where one user is registered while the other is not yet using a three step process:


Alice sends a team invitation to Bob.
Bob accepts the team invitation and registers with the server, providing the server with his public key.
Alice then asks the server for Bob's public key, encrypts the team secret and sends it to the server for Bob (who is now a member of Alice's team) to download.


Bob can now get the encrypted team secret from the server and decrypt it with his private key.

I am trying to reduce this team secret exchange to only two steps. Often times Alice will forget to come back and perform step 3 and would prefer to send the team secret in a secure way at the time of inviting Bob. This is simple to do if Bob was already registered with the server (the encrypted team secret could just be part of the invitation), but often times Bob is not yet registered.

Is there a way that I can perform this team secret exchange in a secure way using only two steps from the user? The server can be used as an intermediary to facilitate the exchange, but should not be able to read the secret.
Without changing an assumption somewhere, it does not look possible.

Here is what your ideal protocol would look like:


Alice sends the invitation to the server (to pass along to Bob), along with a message that is encrypted somehow, but not bound to Bob (as Alice doesn't have anything from Bob to distinguish him from anyone else)
Bob gets the invitation, and the encrypted message, and somehow (without any further interaction from Alice) decrypts the message


The problem is with step two; if Bob can decrypt the message, why can't anyone else (in particular, why can't the server)?  The server knows everything that Alice knows about Bob, and so the server can perform the decryption operation just as well as Bob can.

Now, a similar problem lies in the original protocol; when Alice downloads Bob's public key, the server could provide his own (and when Alice uploads the encrypted message, the server decrypts it, and reencrypts it with Bob's public key).  You did say that the 'untrusted' server can be trusted not to do this.

Obvious ways to address this:


Change the trust assumption; you already trust the server to be honest about public keys; also trust the server not to be malicious about reading intermediate mail (and with this assumption; Alice can encrypt the message with the server's public key, and have the server reencrypt it with Bob's when he downloads it).
Give Alice something from Bob (even a symmetric key) that the server doesn't know.