A method and device for distributing public key infrastructure (PKI) certificate path data enables relying nodes to efficiently authenticate other nodes in an autonomous ad-hoc network. The method includes compiling, at a certificate path management unit (CPMU), the PKI certificate path data (step 405). One or more available certificate paths are then determined at the CPMU for at least one relying node (step 410). Next, the PKI certificate path data are distributed by transmitting a certificate path data message from the CPMU to the at least one relying node (step 415). The certificate path data message includes information identifying one or more trusted certification authorities associated with the one or more available certificate paths.