Methods and apparatus, including computer program products, implementing and using techniques for exchanging certificates, including generating a first container object including one or more of a sender's certificate and a request for a recipient's certificate, wherein the first container object has a recognizable container type, and transmitting the first container object to a recipient's address. Upon receipt of the first container object, it can be determined the first container object includes one or more of a certificate and a request for a certificate of the recipient. A request for a certificate can be responded to by generating a second container object including a certificate of the recipient, extracting a return address from the first container object, and transmitting the second container object to the return address.