One embodiment of the present invention provides a system that uses a portable security token (PST) to facilitate cross-certification between a first certification authority (CA) and a second CA, wherein the first CA and associated subscriber devices constitute a first public-key infrastructure (PKI) domain, and wherein the second CA and associated subscriber devices constitute a second PKI domain. During operation, the system uses the PST to transfer certification information between the first CA and the second CA, wherein the PST communicates with the first CA and the second CA through a location-limited communication channel. Next, the system uses the certification information to issue a cross-certificate to the first CA. Note that the cross-certificate is signed by the second CA. Finally, the system propagates the cross-certificate from the first CA to the associated subscriber devices in the first PKI domain, thereby allowing the associated subscriber devices in the first PKI domain to authenticate themselves to the devices in the second PKI domain.