A method, performed by a registrar of a presence service, for registering a user with a presence service. The method entails negotiating a key with a client device operated by the user in order to establish an encrypted communications channel between the client device and the registrar via a proxy node, authenticating the user by exchanging messages through the encrypted communications channel and through a separate e-mail channel, binding a universally unique identifier identifying the user with one particular function node that is interposed between the proxy node and a publish-subscribe subsystem of the presence service and creating a user profile for the user and storing the user profile in a persistent data store.