In MANET?s self-organized public-key management scheme the certification repository update policy just considers the load balance, so the efficiency of the certificate repository updating service is low. This paper presents an efficient certificate update protocol based on probabilistic reliable multicast. The new scheme includes two parts: (1) Transmission of the update information based on probabilistic reliable multicast; (2) The distributed update request service. In the first part, after the node has created the update information, it first selects some reliable nodes from its local certificate repository which has already had some route information in the local route table, then multicasts the update information to selected nodes. In the second part, after having finished the transmission, the node that has not received the new update information can get the certificate update service from the node that has received the update information instead of the certificate issuer itself. It fully makes use of the existing route information to reduce the traffic cost of searching route information, and reduces the load of the certificate issuer achieving load balance by distributing the service task among multi-nodes in the network, and improves the availability of service. It also provides predictable probabilistic analysis of the scheme?s efficiency.