An apparatus and method is provided for allowing users to share services without sharing identities. Specifically, the apparatus and method allow users to share pseudonyms instead of actual user names, thus protecting both users from unwanted emails, IM messages, and the like. The invention provides an introduction scheme, which comprises a simple and secure way of establishing a user to user link. A preferred embodiment incorporates services of a linked federation network service, such as AOL's Liberty Alliance service, without exposing real user names to other users.