An automated mechanism is provided for generating and distributing appropriate certificates for end entities in a distributed public key infrastructure environment based on trust relationships between the endpoints. Policies between trust zones are specified as an arbitrary graph, referred to as a trust graph. A password is assigned to a trust zone or an individual endpoint by the Certificate Authority. When an endpoint requests a certificate using the appropriate password, the certificate authority uses this graph to generate the appropriate certificates for the endpoint. The distribution of certificates is automated using the Certificate Management Protocol.