The TextSecure Protocol
TextSecure's upcoming iOS client (and Android data channel client) uses a simple trick to provide asynchronous messaging while simultaneously providing forward secrecy.
At registration time, the TextSecure client preemptively generates 100 signed key exchange messages and sends them to the server. We call these "prekeys". A client that wishes to send a secure message to a user for the first time can now:
Connect to the server and request the destination's next "prekey."
Generate its own key exchange message half.
Calculate a shared secret with the prekey it received and its own key exchange half.
Use the shared secret to encrypt the message.
Package up the prekey id, the locally generated key exchange message, and the ciphertext.
Send it all in one bundle to the destination client.
The user experience for the sender is ideal: they type a message, hit send, and an encrypted message is immediately sent.
The destination client receives all of this as a single push notification. When the user taps it, the client has everything it needs to calculate the key exchange on its end, immediately decrypt the ciphertext, and display the message.
With the initial key exchange out of the way, both parties can then continue communicating with an OTR-style protocol as usual. Since the server never hands out the same prekey twice (and the client would never accept the same prekey twice), we are able to provide forward secrecy in a fully asynchronous environment.