Public key validation service

A public key validation agent (PKVA) (701) includes a registration authority (702) which issues a first unsigned public key validation certificate (unsigned PKVC) (800) off-line to a subject (706) that binds a public key (801) of the subject to a first public key serial number (PKVN) (802). The registration authority maintains a certificate database of unsigned PKVCs in which it stores the first unsigned PKVC. A credentials server (703) issues a short-lived disposable public key validation certificate (disposable PKVC) (900) on-line to the subject. The disposable PKVC binds the public key of the subject from the first unsigned PKVC to the first PKVN from the first unsigned PKVC. The credentials server maintains a hash table (704) that contains entries corresponding to valid unsigned PKVCs stored in the certificate database. The PKVA can be employed in a public key validation service to validate the public key of the subject.