One embodiment of the present invention provides a system for managing public keys through a server that stores associations between public keys and email addresses. This system operates by receiving a first message from a client containing a request for approval of a client public key along with the client public key. In response this request for approval, the system sends a second message to the client containing a request for identity confirmation that includes the client public key. If a third message is received from the client containing an affirmative response to the request for identity confirmation, the system stores an association between a client email address and the client public key in a database. This allows other clients to look up the client public key in the database.