The government PKI actually almost exists already. Passports have an rfid chip inside them that does something like receive a challenge and respond with a sign

The government PKI actually almost exists already. Passports have an rfid chip inside them that does something like receive a challenge and respond with a signature over a hash of the passports biographical data combined with the challenge, along with the public key corresponding to the signing key, and a certificate signed by a government key to confirm the signing key is legit. The government public keys are published, so anybody can verify that someone who claims to have possession of a particular passport really does. The weak point is that as far as I can tell the revocation list is not public, so you can't distiguish between a stolen and not stolen passport.