S/MIME is extremely well suited for this, because it's already supported in many clients natively. You could make it possible to obtain a validated identity (e-

S/MIME is extremely well suited for this, because it's already supported in many clients natively. You could make it possible to obtain a validated identity (e-mail validation) from a CA. Many of today's clients would natively be able to verify and trust this identity without previous key exchange. You could still slap arbitrary additional verification on top of this - trust-on-first-use, WoT, whatever you feel like - but an attacker would first have to overcome the (relatively weak) CA validation and then the additional fancy thing, while it would be usable for normal users immediately. The only open issue would be multiple identities and joining them. This could be fixed by sharing the key (i.e. if you generate a key on your phone, tablet and PC, you'd have to take each of the three keys and place a copy on the other two devices).