A messaging service is enhanced by using a trusted third party to exchange the identifiers of the communication partners by pseudonyms.