[leesalminen]

Couldn't they store encrypted messages on their servers but not store any keys? They'd just need a mechanism to privately share they key between devices (Bluetooth pairing)?

[spacehome]

Or every device has a different key, a la iMessage, which in my opinion is better so long as everyone has Apple devices.