They seem to use a public key method. How I would do it was by distributing keys to devices at login and let friends use a users public key to encrypt messages

They seem to use a public key method. How I would do it was by distributing keys to devices at login and let friends use a users public key to encrypt messages to him. Now you pack that encrypted message in a metadata envelope, send to server to be later retrieved by the owner. The keys should never leave the device.