Some embodiments provide a method for providing public keys for encrypting data. The method receives (i) a first request from a first source for a public key associated with a particular user and (ii) a second request from a second source for the public key associated with the particular user. In response to the first request, the method distributes a first public key for the particular user to the first source. In response to the second request, the method distributes a second, different public key for the particular user to the second source. Data encrypted with the first public key and data encrypted with the second public key are decrypted by a device of the particular user with a same private key.